백준 2629번 : 양팔저울

• 분류: 다이나믹 프로그래밍

코드

#include <iostream>
using namespace std;

int n;
int table[31][40001] = {0,};
int weight[31];

bool dp(int num, int goal) {
    if(num==1) {
        if(weight[1]==goal || goal==0) return true;
        else {
            table[num][goal] = -1;
            return false;
        }
    }
    if(table[num][goal]==1) return true;
    else if(table[num][goal]==-1) return false;
    if(goal==weight[num]) return true;
    if(goal==0) return true;

    if(table[num-1][goal]==1) return true;
    if(table[num-1][goal]==0) {
        if(dp(num-1, goal)) return true;
        else table[num-1][goal] = -1;
    }
    if(table[num-1][goal+weight[num]]==1) return true;
    if(table[num-1][goal+weight[num]]==0) {
        if(dp(num-1, goal+weight[num])) return true;
        else table[num-1][goal+weight[num]] = -1;
    }
    if(table[num-1][abs(goal-weight[num])]==1) return true;
    if(table[num-1][abs(goal-weight[num])]==0){
        if(dp(num-1, abs(goal-weight[num]))) return true;
        else table[num-1][abs(goal-weight[num])] = -1;
    }
    table[num][goal] = -1;
    return false;
}

int main() {
    for(int i=0 ; i<31 ; i++) for(int j=0 ;j<40001 ; j++) table[i][j]=0;
    cin >> n;
    for(int i=1 ; i<=n ; i++) cin >> weight[i];

    int t;
    cin >> t;
    for(int i=0 ; i<t ; i++) {
        int goal;
        cin >> goal;

        if(dp(n, goal)) cout << "Y\n";
        else cout << "N\n";
    }
}

• 코멘트
  
  

추 n개(인덱스 1~n)를 가지고 A를 재야 한다.

추 중에 가장 큰거를 M0 라고 하면 –> 추 (n-1)개를 가지고 A, A+M0, A-M0을 잴 수 있는가?

그 다음 큰거를 M1 라고 하면 –> 추 (n-2)개를 가지고 A, A+M1, A-M1, A+M0+M1, A+M0-M1, A-M0+M1, A-M0-M1 을 잴 수 있는가?

…

두번째로 작은거를 M(n-2) 라고 하면 –> 추 1개를 가지고 ~~~ 를 잴 수 있는가? 즉, 남은 1개의 추와 후보 무게가 같은가?

대략 이런 아이디어로 접근할 수 있다. 목표 goal에서 weight[k]를 더하거나, 빼거나, 냅두거나 하면서 k=1~n으로 탐색해 나간다.
가장 밑바닥에서는 goal과 weight[1] 이 같은지, 또는 goal==0인지 확인한다.