양팔저울

문제 링크

발상

주어진 물건을 적절하게 골라 특정한 무게를 만들어야 한다는 점에서 평범한 배낭 문제의 바리에이션인게 바로 느껴진다. 단, 추에 별도의 가치값은 없고 무게만 있으며, 무게를 단순히 더하기만 하는게 아닌 뺄 수도 있다는 점이 다르다. ( 구슬의 반대편에 추를 놓으면 무게를 빼는 것과 같다. ) 이전 문제와 구조가 동일하므로 점화식을 적절하게 수정해 해결할 수 있다.

점화식

$$\{\begin{array}{l}{n}_{i,j}=\text{i번째 추까지만 사용해 무게 j를 만들 수 있는지 여부}\\ w_i=\text{i번째 추 무게}\end{array}$$ $$n_{i,j}=n_{i-1,j}\vee n_{i-1,|j-w_i|}\vee n_{i-1,j+w_i}$$

$\vee$기호는 OR 논리 연산자이다. 이전 추까지 사용한 무게 리스트에서 현재 추의 무게를 빼는 것, 더하는 것, 아예 사용하지 않는 것까지 총 3개의 경우 중 하나라도 만족하면 해당 무게를 만들 수 있다.

코드

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int main() {    
    int n; cin >> n; vector<int> arr(n + 1); int s = 0;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i]; s += arr[i];
    }
    vector<vector<int>> dp(n + 1, vector<int>(s + 1, -1));    
    dp[1][0] = 1;
    dp[1][arr[1]] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= s; j++) {
            dp[i][j] = dp[i - 1][abs(j - arr[i])] == 1 ? 1 : dp[i][j];
            if (j + arr[i] <= s) {
                dp[i][j] = dp[i - 1][j + arr[i]] == 1 ? 1 : dp[i][j];
            }
            dp[i][j] = dp[i - 1][j] == 1 ? 1 : dp[i][j];
        }        
    }
    int k; cin >> k;
    while (k--) {
        int q; cin >> q;
        if (q > s) cout << 'N' << " ";
        else cout << (dp[n][q] == 1 ? 'Y' : 'N') << " ";
    }    
    return 0;
}