※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
$dp[i][j] = i$번 째 추를 사용할 때, 무게가 $j$인 경우
예를 들어
1,1,3,4,2 의 추가 존재한다고 한다면
1+1+3, 1+4 의 경우로 5번째까지 올 수 있습니다. 이 경우 그 뒤의 추가 중복되어서 계산되므로 이를 메모이제이션하여 시간을 단축할 수 있습니다.
$i$번 째 추에 대해서는
1) 이 추만을 사용하는 경우
2) 이 추를 사용하지 않는 경우
3) 이 추를 누적하여 사용하는 경우
의 3가지로 나누어 볼 수 있습니다.
그 뒤 중요한 것이, 구슬이 올라갈 위치의 저울에도 추를 올릴 수 있으므로 구슬의 무게+임의의 추의 무게 의 합에 대한 무게를 잴 수 있는지 체크하여 1번이라도 잴 수 있다면 Y를 출력하면 됩니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
int n, m, k, ps, w[31];
bool dp[31][150001];
void dfs(int pos, int wei)
{
if (pos == n || dp[pos][wei]) return;
dp[pos][wei] = true;
dfs(pos + 1, w[pos+1]);
dfs(pos + 1, wei);
dfs(pos + 1, wei + w[pos+1]);
}
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) cin >> w[i], ps += w[i];
dp[n - 1][0] = true;
dfs(0, w[0]);
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> k;
bool f = false;
for (int j = 0; j <= ps; j++)
{
if (j + k > ps) break;
if (dp[n - 1][j] && dp[n - 1][j + k])
{
f = true;
break;
}
}
cout << (f ? "Y " : "N ");
}
}