Problem Solving/BOJ 백준
[ BOJ 백준 2629번 - 양팔저울 ] 해설 및 코드
재미지
2019. 12. 9. 17:33
https://www.acmicpc.net/problem/2629
2629번: 양팔저울
첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있 다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는
www.acmicpc.net
목적
주어진 추 N개를 이용하여 측정할 수 있는 모든 무게를 구한다.
접근법
1. a[i]는 i 번째 추의 무게이고, s[i]는 1~i번째 추를 사용하여 만들 수 있는 무게라고 가정할 때, s[i]를 다음과 같이 나타낼 수 있다.
- s[i-1]
- s[i-1] + a[i]
- abs(s[i-1] - a[i])
즉, 이전까지 만든 무게에 현재 idx에 해당하는 추의 무게를 가할지, 감할지, 아무작업도 안 할지의 세가지로 측정가능한 무게를 만들어낼 수 있다.
2. 위의 점화식을 사용하여 재귀적으로 알고리즘을 구현하고, 중복 연산을 막기 위한 작업도 해준다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include<iostream>
#include<cmath>
using namespace std;
int n,weights[31];
bool measurable[15001]={}, measured[31][15001]={};
void measure(int i,int weight){
if(i>n) return;
if(measured[i][weight])return;
measured[i][weight]=true;
measurable[weight]=true;
measure(i+1,weight);
measure(i+1,weight+weights[i]);
measure(i+1,abs(weight-weights[i]));
}
int main(){
cin>>n;for(int i=0;i<n;++i)cin>>weights[i];
measure(0,0);
int t;cin>>t;
while(t--){
int ball;cin>>ball;
if(ball<=15000&&measurable[ball])cout<<'Y';
else cout<<'N';
cout<<' ';
}
}
|
