(백준/ C++) 2629 - 양팔저울

 

"(백준/ C++) 2629 - 양팔저울"

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

 

아마 .. 양팔저울 문제 설명에 냅색 알고리즘으로 푸는 문제라고 적혀 있지 않으면 오랫동안 못 풀었을거 같다.. ^^;;

 

 

냅색과 같이 나올수 있는 무게의 경우를 만드는 방식으로 풀이를 했다. 

점화식은 (가)저울에만 추를 둘수 있다고 생각 하고 경우의 수를 고려하였다. 

1. (가)에 A추가 있는 경우 → (가) A추 + 구슬 = (나) B추 → (가) 구슬 = (나) B추  -  A추
2. (나)에 A추가 있는 경우 → (가) 구슬 = (나) B추 + A추
3. (가), (나)에 A추가 모두 없는 경우 → (가) 구슬 = (나) B추

 

처음에는 이분탐색으로 찾으려 했으나 메모리 문제로 실패 ! DP[비교대상개수][무게]로 풀자!

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

int gN, gTC;
int gWeight[31];
//vector<int> gAllSum;
bool dp[31][15001];

void DFS(int pParm01, int pParm02)
{
	if (pParm01 > gN || dp[pParm01][pParm02])
	{
		return;
	}

	dp[pParm01][pParm02] = true;

	DFS(pParm01 + 1, pParm02);
	DFS(pParm01 + 1, abs(pParm02 - gWeight[pParm01]));
	DFS(pParm01 + 1, pParm02 + gWeight[pParm01]);
}

int main(void)
{
	cin >> gN;

	for (int idx = 0; idx < gN; ++idx)
	{
		cin >> gWeight[idx];
	}
	DFS(0, 0);

	//std::sort(gAllSum.begin(), gAllSum.end());

	cin >> gTC;

	for (int idx = 0; idx < gTC; ++idx)
	{
		int mTc;
		cin >> mTc;
		if (mTc > 15'000)
		{
			cout << "N";
		}
		else if (dp[gN][mTc])
		{
			cout << "Y";
		}
		else
		{
			cout << "N";
		}
	}
	return 0;
}