[boj] 백준 2629 양팔저울 (c++) - dp, 재귀

[문제]

https://www.acmicpc.net/problem/2629

2629번: 양팔저울

 

[풀이]

예시처럼 1g, 4g 추가 각각 있다고 할 때 구할 수 있는 구슬의 무게는 다음과 같다.

1) 1g, 4g 각각 하나씩 올려놓았을 때 구할 수 있는 구슬의 무게 1g, 4g

2) 1g, 4g 추를 같은 편에 올려놓았을 때 구할 수 있는 구슬의 무게 1+4=5g

3) 1g, 4g 추를 다른 편에 올려놓았을 때 구할 수 있는 구슬의 무게 4-1=3g

 

즉, 올려놓는 추의 개수 cnt를 증가시켜가며 추를 올려놓는 경우, 안 올려놓는 경우, 구슬이 있는 편에 올려놓는 경우에 대해 재귀함수를 호출하면 된다. 

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#define INF 987654321

using namespace std;

int n, m;
bool dp[31][15001]; //i번째까지 추를 올렸을 때, j의 무게를 만들 수 있는지
int weight[31];

void solve(int cnt, int w){
    if(cnt > n || dp[cnt][w]) return;
    dp[cnt][w] = true;

    solve(cnt+1, w+weight[cnt]);
    solve(cnt+1, w); //추를 안올리는 경우
    solve(cnt+1, abs(w-weight[cnt])); //구슬이 있는 쪽에 올리는 경우
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i=0; i<n; i++){
        cin >> weight[i];//추의 무게
    }

    solve(0, 0);

    cin >> m;
    for(int i=0; i<m; i++){
        //확인하고자 하는 구슬의 무게
        int temp;
        cin >> temp; //구슬의 무게가 확인 가능하면 Y, 불가능하면 N

        if(temp > 15000) cout << "N ";
        else if(dp[n][temp]) cout << "Y ";
        else cout << "N ";
    }
}