[알고리즘] 백준 2629 - 양팔저울

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int N, M, Arr[31];
bool dp[31][15001];

void solve(int a, int b){
    if(a > N || dp[a][b]){
        return;
    }
    dp[a][b] = true;
    
    solve(a + 1, b + Arr[a]);
    solve(a + 1, abs(b - Arr[a]));
    solve(a + 1, b);
    
    return;
}

int main(){
    cin >> N;

    for(int i=0; i<N; i++){
        cin >> Arr[i];
    }

    solve(0, 0);

    cin >> M;

    int cnt;
    for(int i=0; i<M; i++){
        cin >> cnt;

        if(cnt > 15000){
            cout << "N ";
        }
        else if(dp[N][cnt]){
            cout << "Y ";
        }
        else{
            cout << "N ";
        }
    }
    cout << "\n";
    return 0;
}