https://www.acmicpc.net/problem/2629
하나의 추를 다음 세가지 경우로 사용할 수 있다.
- 추를 구슬과 반대 방향에 둔다.
- 추를 구슬과 같은 방향에 둔다.
- 추를 사용하지 않는다.
재귀함수를 사용해서 첫번째 추부터 N번째 추까지 경우를 따졌고, 여기서 나온 결과를 배열 bool table[i][j] : i는 마지막으로 사용한 추, j는 i까지 사용했을때 표현 가능한 무게로 정의해서 table에 저장했다. 마지막에 table[N][x]만 확인하면 가지고 있는 추로 무게 x를 표현할 수 있는지 알 수 있다.
구슬의 최대 무게가 40000인데 table 크기를 table[N+1][40000]으로 잡으면 틀렸습니다로 나온다..;;; ㅜ
#include <iostream>
#include <algorithm>
using namespace std;
int N,M,x;
int weight[31];
bool table[31][40001];
void solve(int i, int w){
if(i>N || table[i][w]) return;
table[i][w] = true;
solve(i+1, w+weight[i]);
solve(i+1, abs(w-weight[i]));
solve(i+1, w);
return ;
}
int main(){
cin>>N;
for(int i=0; i<N; i++) cin>>weight[i];
solve(0, 0);
cin>>M;
for(int i=0; i<M; i++) {
cin>>x;
string ans="N ";
if(table[N][x]) {
ans="Y ";
}
cout<<ans;
}
}