백준 2629 c++ : DP, DFS, 냅색

너무 안 풀려서 다른 풀이를 참고했다. 처음에는 DP, 냅색으로 풀어보려 했지만, 조합을 찾는다는 개념으로 DFS로 접근하는 방법도 알게 됐다.
전역변수를 안쓰고 싶었는데, 안쓰게 되면 매개변수가 너무 많아져서 보류했다.

참고 : https://cclient.tistory.com/122

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int weight_N, bead_N;
int weight[31];
bool dp[31][15001];

void input_weight() {
	int i;

	cin >> weight_N;
	for (i = 0; i < weight_N; i++) {
		cin >> weight[i];
	}
}

void DFS(int A, int B)
{
	if (A > weight_N || dp[A][B])
	{
		return;
	}

	dp[A][B] = true;

	DFS(A + 1, B);
	DFS(A + 1, abs(B - weight[A]));
	DFS(A + 1, B + weight[A]);
}

void find_answer() {
	int i, bead;
	
	cin >> bead_N;
	for (i = 0; i < bead_N; i++)
	{
		cin >> bead;
		if (bead > 15000)
		{
			cout << "N ";
		}
		else if (dp[weight_N][bead])
		{
			cout << "Y ";
		}
		else
		{
			cout << "N ";
		}
	}
	
	return;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input_weight();
	DFS(0, 0);
	find_answer();

	return 0;
}