[BOJ] 2629 양팔저울

DP 정의는 $DP(i,j)$=i 이하 번호의 추를 사용하여 왼쪽 저울 - 오른쪽 저울의 무게가 j가 되게 할 수 있는가

그러면 $DP(i,j)=DP(i+1,j+weight[i]) || DP(i+1,j-weight[i]) || DP(i+1,j)$라는 점화식이 세워짐. 왼쪽에 올리거나, 오른쪽에 올리거나, 아예 올리지 않거나. 간단한 DP problem

#include <bits/stdc++.h>
 
using namespace std;
 
int f(int x)
{
    return x+60000;
}
 
int n,m;
int weight[35];
int cache[35][120000];
 
int dp(int idx, int w)
{
    if(idx==n)
    {
        if(w==f(0)) return 1;
        else return 0;
    }
 
    int& ret=cache[idx][w];
    if(ret!=-1) return ret;
 
    int ma=0;
    ma=max(ma,dp(idx+1,w+weight[idx]));
    ma=max(ma,dp(idx+1,w-weight[idx]));
    ma=max(ma,dp(idx+1,w));
    return ret=ma;
}
 
int main()
{
    memset(cache,-1,sizeof(cache));
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&weight[i]);
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        int t;
        scanf("%d",&t);
        printf("%c ",dp(0,f(t))?'Y':'N');
    }
    return 0;
}