백준 2629 양팔저울

링크텍스트

냅색 알고리즘을 사용하면 쉽게 풀 수 있는 문제다.

choo[num] == weight
dp(num - 1, weight)
dp(num - 1, weight - choo[num])
dp(num - 1, weight + choo[num])
dp(num - 1, choo[num] - weight)
dp(num - 1, choo[num] + weight))
중에서 하나만 참을 반환하면 해당 추를 사용해서 구슬의 무게를 구할 수 있다.

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

int N, M; // 추 개수, 구슬 개수
int choo[31]; 
int goosle[8];
int cache[31][40001];
int sum = 0;

int dp(int num, int weight) {
	if (weight == 0)return 1;
	if (weight > 40000 || weight > sum || num<0 ||weight <0) return 0;

	int& res = cache[num][weight];
	if (res != -1) return res;
	
	if (choo[num] == weight || dp(num - 1, weight) || dp(num - 1, weight - choo[num]) || dp(num - 1, weight + choo[num]) || dp(num - 1, choo[num] - weight) || dp(num - 1, choo[num] + weight)) res = 1;
	else res = 0;

	return res;
}
int main(void) {
	
	for (int i = 0; i < 31; i++)fill(cache[i], cache[i] + 40001, -1);
	
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> choo[i];
		sum += choo[i];
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> goosle[i];
		if (dp(N - 1, goosle[i])) {
			cout << "Y ";
		}
		else {
			cout << "N ";
		}
	}

	return 0;


}