백준 2629번 양팔저울

문제 링크

DP 문제다. 문제를 단순화해서, 구슬은 항상 저울의 왼쪽에 위치한다고 생각해보자. 이 때 추를 오른쪽에 놓으면 구슬의 무게가 올라가야하고, 추를 왼쪽에 놓은 구슬의 무게가 내려가야한다. 이 두 가지 경우에 대해 계산해주면 된다.

음수 무게도 만들수 있다고 가정해야 문제를 풀 수 있다. 여기에 더 큰 추를 오른쪽에 놓아서 결국 양수가 될 수 있기 때문이다

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int MAX = 15001;
bool dp[30][30005];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n;
    vector<int> v(n);
    for (auto& x : v) {
        cin >> x;
    }
    cin >> m;
    vector<int> cv(m);
    for (auto& x : cv) {
        cin >> x;
    }

    dp[0][MAX+v[0]] = 1;
    dp[0][MAX-v[0]] = 1;

    for (int i = 1; i < n; i++) {
        dp[i][MAX+v[i]] = 1;
        dp[i][MAX-v[i]] = 1;
        for (int j = 0; j <= 30003; j++) {
            dp[i][j] += dp[i-1][j];
            if (j >= v[i]) {
                dp[i][j-v[i]] += dp[i-1][j];
                dp[i][j] += dp[i-1][j-v[i]];
            }
        }
    }

    for (auto x : cv) {
        if (x >= MAX) cout << "N ";
        else if (dp[n-1][x+MAX]) cout << "Y ";
        else cout << "N ";
    }

    return 0;
}

가운데 MAX를 기준으로 양수, 음수를 나눈다. 추 30개에 대해 전부 다음과 같이 계산한다.

1. 추 하나만 왼쪽에 놓는 경우, 오른쪽에 놓는 경우 계산
2. 지금까지 만들어진 무게들에 대해 왼쪽에 놓는 경우, 오른쪽에 놓는 경우 계산

Knapsack DP는 탑다운으로 풀기 힘들고, 바텀업으로 푸는게 훨씬 잘 풀린다. 왜 그런지는 다음에 포스팅할 예정이다.