알고리즘
- 모든 경우를 따지기 위해서 각 추가 구슬 반대쪽에 올라가는 경우, 저울에 안올라가는 경우, 구슬과 같은 쪽에 올라갈 경우를 모두 고려해야함
배낭문제를 응용하여, 추를 하나씩 모든 무게에 대해 검사를 한다.
- true이면 구슬 반대쪽 저울에 추만으로 만들 수 있는 무게라는 뜻.
- 현재 추를 사용하여 만들 수 있는 무게면 true표시
- 현재 추를 사용하지않고 이전 추로만으로도 만들 수 있는 무게면, 현재추를 구슬과 같은 저울에 놓고 만들 수 있는 무게도 true 표시
- 위 알고리즘을 진행 후 마지막 줄에 가능한 모든 경우에 true가 표시되어있다.
코드
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
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std;
int n, w[30];
bool check[31][15001];
int abs(int a) {
return a < 0 ? -a : a;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> w[i];
for (int i = 0; i <= 30; i++)
check[i][0] = true;
for (int j = 1; j <= n; j++) {
for (int i = 1; i <= 15000; i++) {
if (w[j - 1] <= i && check[j - 1][i - w[j - 1]]) {
check[j][i] = true;
}
else if (check[j - 1][i]) {
check[j][i] = true;
check[j][abs(i - w[j - 1])] = true;
}
}
}
int c, t;
cin >> c;
for (int i = 0; i < c; i++) {
cin >> t;
if (t > 15000)
cout << "N ";
else if (check[n][t])
cout << "Y ";
else
cout << "N ";
}
}