[c++] 백준 2629 양팔저울

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

2629번: 양팔저울

dp[i][j]

" j번째 추까지 고려했을때 i의 무게를 판별 가능한가 "

dp 테이블의 상태값을 이렇게 잡았다.

이 뒤로는 쉽다.

만약 j번째 추를 이용해 무게를 구하려 할 때 가능한 무게를 생각해보자.

j-1번째에서 j번째 추를 추가 할 때

j번쨰 추의 무게를 weight[j],

j-1번째 번째에서 만들 수 있는 무게를 k라고 하면,

만들수 있는 무게는

weight[j] + k 또는 abs(weight[j] - k) 임을 알 수 있다.

따라서 점화식은

1. dp[weight[j]+i][j] = 1;

2. dp[abs(weight[j]-i)][j] = 1;

3. dp[i][j] = 1;

이다.

#include<bits/stdc++.h>
using namespace std;
int weight[33];
bool dp[44444][33];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin>>n;
    for(int i=1; i<=n; i++)
        cin>>weight[i];
    dp[weight[1]][1] = 1;
    for(int j=2; j<=n; j++){
        dp[weight[j]][j] = 1;
        for(int i=1; i<=40000; i++){
            if(dp[i][j-1]){
                dp[weight[j]+i][j] = 1;
                dp[abs(weight[j]-i)][j] = 1;
                dp[i][j] = 1;
            }
        }
    }
    int m; cin>>m;
    while(m--){
        int ball; cin>>ball;
        if(dp[ball][n]) cout << "Y ";
        else cout << "N ";
    }
    return 0;
}