백준 2629 양팔저울

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

2629번: 양팔저울

DP를 이용해 푸는 문제였습니다.

추의 개수가 30이므로 추가 올라갈 수 있는 모든 경우의 수를 고려하기에는 시간복잡도가 매우큽니다.

O(2^30) 따라서 우리는 구슬과 추의 무게범위가 크지 않은 것을 이용해야합니다. 

DP를 통해 무게에 대한 경우의 수로 바꿔야합니다. 따라서 모든 추를 어떤 무게에 대해서 더하고 빼는 것으로 경우의 수를 셀 수 있습니다. 배열의 크기를 정할때 중요한 것은 무게를 빼고 더할때 구슬과 비교할떄의 상대적 무게를 구하는것이므로 음수를 고려해야합니다.

#include<stdio.h>
#include<queue>
#include<vector>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<algorithm>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int choo[31];
int N,Q;
bool chk[160001];
int main(){
    fast_io();
    cin>>N;
    for(int x=0;x<N;x++) cin>>choo[x];
    cin>>Q;
    sort(choo,choo+N);
    chk[80000]=true;
    for(int y=0;y<N;y++){
        for(int z=160000;z>=0;z--){
            if(chk[z] && z+choo[y]<=160000){
                chk[z+choo[y]]=true;
            }
        }
        chk[y]=true;
    }
    for(int y=0;y<N;y++){
        for(int z=0;z<=160000;z++){
            if(chk[z] && z-choo[y]>=0){
                chk[z-choo[y]]=true;
            }
        }
    }
    for(int x=0;x<Q;x++){
        int input;
        cin>>input;
        if(chk[80000+input] || chk[80000-input]) cout<<"Y ";
        else cout<<"N ";
    }
}