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

문제 링크입니다. https://www.acmicpc.net/problem/2629

2629번: 양팔저울

배낭문제를 이용한 Dp 문제입니다.

주어진 추의 무게를 통해 원하는 구슬 무게를 잴 수 있는지 물어보는 문제입니다.

 

다른 배낭 알고리즘을 이용한 문제와 달리, 이 문제의 특이한 점은 추를 반대편에서 달 수 있다는 점입니다.

따라서, X무게에서 새로운 추를 놓을 때,  X+Y or X-Y의 무게를 두개다 잴 수 있습니다.

 

또한, N개의 추를 이용해 잰다고 해도, 이전에 잴 수 있었던 무게도 포함해야합니다.

왜냐하면, N개만을 이용해 무게를 잰다고 할 때, 모든 경우를 잴 수 없기 때문입니다.

예를 들어보겠습니다.

(2, 2, 5, 6, 7)의 무게를 가진 추가 있다고 해보겠습니다.

3개를 사용해 무게를 잴 때, (2, 2, 5) / (2, 2, 6) 등의 무게를 잴 수 있습니다.

하지만, 6은 4번째 추이기에 (2, 2)만을 가지고 무게를 잴 수 없습니다.

이를 해결하기 위해서는 N번째이더라고 1~N-1까지 잴 수 있던 무게를 모두 저장해줘야 합니다.

 

 

아래 코드는 문제의 점화식입니다.

for(int i = 1; i <= N; i++){
        dp[i][weight[i]] = 1;
        for(int j = 1; j <= sum; j++){ //모든 추의 무게까지 확인해본다.
            if(j-weight[i] >= 0){
                if(dp[i-1][j-weight[i]] == 1){ //j의 무게를 만들 수 있다면?
                    dp[i][j] = 1;
                }
            }
            if(dp[i-1][j] == 1){ // j의 무게가 이전에 만들어졌다면
                dp[i][abs(j-weight[i])] = 1; // 반대쪽에 놨을 경우
                dp[i][j] = 1;                // I번째에도 j값을 저장한다.
            }
        }
    }

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <cstring>
#define P pair<int, int>
#define F first
#define S second
#define INF 987654321;

using namespace std;

int N, M, sum;
int weight[31];
int dp[31][15001];

void solve(){
    for(int i = 1; i <= N; i++){
        dp[i][weight[i]] = 1;
        for(int j = 1; j <= sum; j++){
            if(j-weight[i] >= 0){
                if(dp[i-1][j-weight[i]] == 1){
                    dp[i][j] = 1;
                }
            }
            if(dp[i-1][j] == 1){
                dp[i][abs(j-weight[i])] = 1;
                dp[i][j] = 1;
            }
        }
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> weight[i];
        sum += weight[i];
    }
    solve();
    cin >> M;
    for(int i = 1; i <= M; i++){
        int x;
        cin >> x;
        if(x > 15000) cout << "N ";
        else if(dp[N][x] == 1) cout << "Y ";
        else cout << "N ";
    }
    return 0;
}

 

질문 및 조언은 댓글을 남겨주세요