[백준 / C++] 2629번: 양팔저울

백준 2629번: 양팔저울
알고리즘 분류: 다이나믹 프로그래밍, 배낭 문제

백준 문제 바로가기

🤨 Hmm...

어제 배낭 문제 푼 김에 배낭 문제들이랑 좀 친해져야지

이 문제는 추와 구슬의 조합으로 구슬 무게를 잴 수 있는지에 대한 문제였다.

처음에 추로만 재야되는 줄 알았다가 구슬 하나랑 추를 조합해서 잴 수 있는 것을 깨달았다.

일반적인 배낭 문제는 배열값으로 최댓값 혹은 최솟값을 구하지만 이 문제는 가능한 지만 알면 되기 때문에 0, 1로 표현했다.

dp[i][w] 꼴로 표현했는데, i번째까지 추를 고려하여 w 무게를 측정할 수 있으면 1, 없으면 0으로 표현했다.

그리고 구슬을 입력 받으면서 dp배열의 마지막 행의 구슬 무게(w) 열 값이 1이면 "Y",

0이면 임의의 값에서 구슬 무게를 뺀 무게의 열 값이 1이면 "Y",

그렇지 않다면 "N"을 출력하도록 했다.

몇 번의 디버그를 거쳐 통과!!!

💻 소스 코드

#include <iostream>
#include <memory.h>
#define fastIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

class BJ {
    int wN;
    int weight[31];
    int bN, bead;
    int dp[31][40001];
public:
    BJ();
    void solution();
};

BJ::BJ() {
    cin >> wN;
    int sum = 0;
    for (int i = 1; i <= wN; i++) {
        cin >> weight[i];
        sum += weight[i];
    }

    solution();

    cin >> bN;
    for (int i = 0; i < bN; i++) {
        cin >> bead;
        bool flag = false;
        for (int j = bead; j <= sum; j++) {
            if (j == bead && dp[wN][bead] == 1) { flag = true; break; }
            if (dp[wN][j] == 0) continue;
            if (dp[wN][j-bead] == 1) {
                flag = true;
                break;
            }
        }
        cout << (flag ? "Y " : "N ");
    }

}
void BJ::solution() {
    memset(dp, 0, sizeof(int)*40001);
    for (int i = 1; i <= wN; i++) {
        dp[i][0] = 0;
        for (int j = 1; j <= 40000; j++) {
            if (weight[i] > j)
                dp[i][j] = dp[i-1][j];
            else {
                if (weight[i] == j)
                    dp[i][j] = 1;
                else if (dp[i-1][j-weight[i]] == 1)
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
    }
}

signed main(){
    fastIO;

    BJ Q2629;
}