[백준/BOJ] 백준 2629번 : 양팔저울

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

2629번: 양팔저울

 

확인할 구슬을 왼쪽 저울에 두었다고 생각하고, cache[확인하는 추의 인덱스][왼쪽 저울 무게와 오른쪽 저울 무게의 차이]인 상황일 때, 양쪽의 차이가 0이 될 수 있는지를 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다.

 

코드

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

int n;
vector<int> choo;
int check_n;
vector<int> check;
int cache[35][40000 + 15005]; //[인덱스][왼쪽 저울 무게와 오른쪽 저울 무게의 차이]
vector<string> output;

void init() {
	for (int i = 0; i < 35; i++) {
		for (int j = 0; j < (40000 + 15005); j++) {
			cache[i][j] = -1;
		}
	}
}

int solve(int index, int diff, int left_weight, int right_weight) {

	//왼쪽 저울과 오른쪽 저울의 무게가 같을때
	if (diff == 0) {
		return 1;
	}

	//모든 추를 다 확인 했을때
	if (index == n) {
		return 0;
	}

	int& ret = cache[index][diff];

	if (ret != -1) {
		return ret;
	}
	ret = 0;

	//index 추를 사용하지 않을때
	ret |= solve(index + 1, diff, left_weight, right_weight);

	//index 추를 왼쪽에 둘때
	ret |= solve(index + 1, abs((left_weight + choo[index]) - right_weight), left_weight + choo[index], right_weight);

	//index 추를 오른쪽에 둘 때
	ret |= solve(index + 1, abs(left_weight - (right_weight + choo[index])), left_weight, right_weight + choo[index]);

	return ret;
}

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

	init();

	cin >> n;

	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;
		choo.push_back(input);
	}

	cin >> check_n;

	for (int i = 0; i < check_n; i++) {
		int input;
		cin >> input;

		if (solve(0, input, input, 0) == 1) { //구슬을 처음에 왼쪽 저울에 두었다고 생각
			output.push_back("Y");
		}
		else {
			output.push_back("N");
		}
	}

	for (int i = 0; i < output.size(); i++) {
		cout << output[i] << " ";
	}

	return 0;
}