백준 2629 양팔 저울

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

2629번: 양팔저울

백 트랙킹과 DP를 활용하는 문제다.

 

적은 N과 상대적으로 널럴한 시간 제한을 보자마자 백트랙킹 감이 오긴했으나... 아직 recursion 알고리즘을 짜는 게 미흡한 것 같다.

 

이렇게 ''완전탐색''을 하면 반드시 풀 수 있는 문제를 백트랙킹과 DP로 구현할때는

 

각 케이스에서 발생 가능한 모든 사례를 Recursion으로 처리하는 연습을 해야겠다.

ㅠㅠ

 

/* 양팔 저울 */

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

using namespace std;

int n_of_sinker, n_of_ball;
int sinker[30], s_of_sinker[30 + 1][40000 + 1];

/* 두 개를 더하거나, 두 개를 빼거나, 하나를 반대쪽에 놔두기 */
/* 일단 케이스를 생각해보는거야! */

void recursive(int cur, int hab) {
	if (cur > n_of_sinker) return;
	if (s_of_sinker[cur][hab] == true) return;

	s_of_sinker[cur][hab] = true;

	// 두 개를 더하기
	recursive(cur + 1, hab + sinker[cur]);
	recursive(cur + 1, hab);
	recursive(cur + 1, abs(hab - sinker[cur]));
}


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

	/* Input */
	cin >> n_of_sinker;
	for (int i = 0; i < n_of_sinker; cin >> sinker[i++]);

	recursive(0, 0);

	cin >> n_of_ball;
	for (int i = 0; i < n_of_ball; i++) {
		int target; cin >> target;
		int j;
		for (j = 0; j <= n_of_sinker; j++) {
			if (s_of_sinker[j][target] == true) break;
		}

		if (j > n_of_sinker) cout << "N ";
		else cout << "Y ";
	}

	return 0;
}