[C++] 백준 2629번-양팔저울

BOJ 2629-양팔저울

문제

예제 입력1

2
1 4
2
3 2

에제 출력1

Y N

예제 입력2

4
2 3 3 3
3
1 4 10

에제 출력2

Y Y N

풀이

DP를 사용하여 푸는 문제다.

• 구슬의 무게 + 왼쪽 추의 무게합 = 우측 추의 무게 합 이 성립될 경우 Y를 출력하라는 문제이다.
• 그렇기에 구슬 무게 = 우측 추의 무게합 - 왼쪽 추의 무게합이 점화식이다.
• 추를 놓는 모든 경우의 수 중 우측 추의 무게합 - 왼쪽 추의 무게합이 존재 할 경우 해당 무게와 같은 무게인 구슬이 있으면 해당 구슬은 Y를 출력할 수 있다.
• 모든 경우의 수를 탐색할 경우 시간 초과가 발생할 수 있으므로 flag[무게합][i번 째 추]에 체크해서 중복되는 경우는 넘기도록 한다.

소스코드

#include "bits/stdc++.h"
using namespace std;

int n, m;
int weights[31];
int beads[31];
int answer[50001];
int flag[50001][600];


int DP(int x,int c) {
	if (c >= 50000)
		return 0;
	if (flag[abs(c)][x] == 1)
		return 0;
	if (x > n)
		return 0;
	answer[abs(c)] = 1;
	flag[abs(c)][x] = 1;

	DP(x + 1, c + 0);
	DP(x + 1, c - weights[x]);
	DP(x + 1, c + weights[x]);
	return abs(weights[x]);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> weights[i];
	}

	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> beads[i];
	}
	answer[DP(0, 0)] = 1;

	for (int i = 0; i < m; i++) {
		if (answer[beads[i]] == 1) {
			cout << "Y ";
		}
		else {
			cout << "N ";
		}
	}
}