백준 2629 양팔저울 (C++)

2629번: 양팔저울

배낭 문제를 이용한 dp 문제이다. 각 추마다 0부터 40000까지 반복문을 돌면서 세가지 조건에 따라 dp를 갱신해준다.

• 아무것도 하지 않을 경우
• 현재 무게에서 추의 무게를 뺀 경우
• 현재 무게에서 추의 무개를 더한 경우

dp[i][j]일 때, i는 i번째 추를, j는 무게를 나타낸다. dp[0][0] = true를 해주고 반복문을 돌면서 dp를 갱신을 해주고 난 뒤 각 구슬마다 답을 출력해주었다.
생각보다 어려웠던 문제였다. 기존 배낭 문제에서 변형된 문제였기에 조건을 정하기가 좀 까다로웠다. 배낭 문제를 이용한 이런한 방식에 대해서도 잘 알아두어야 겠다.

#include <iostream>
#include <cmath>

using namespace std;

int N, M;
int w[31], m[7];
bool dp[31][40001];

void solution() {
    dp[0][0] = true;

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= 40000; j++) {
            if (!dp[i - 1][j]) continue;

            dp[i][j] = true;
            if (abs(j - w[i]) >= 0) dp[i][abs(j - w[i])] = true;
            if (j + w[i] <= 40000) dp[i][j + w[i]] = true;
        }
    }

    for (int i = 0; i < M; i++) {
        if (dp[N][m[i]]) cout << "Y ";
        else cout << "N ";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> w[i];
    }

    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> m[i];
    }

    solution();

    return 0;
}