[BOJ-2629] 양팔저울 (C++)

백준 2629 양팔저울

 

2629번: 양팔저울

 

문제 설명

 

 - 양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지 출력하라.

 

 - 구슬이 3g인 경우 1g의 추와 4g의 추로 구슬의 무게를 확인할 수 있다. 

 - 구슬의 무게에 대해 확인이 가능하면 Y, 아니면 N를 차례로 출력하라.

---

 

입력 값

 

 - 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30개 이하이다.

 

 - 둘째 줄에는 추의 무게들은 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게가 있을 수 있다.

   추의 무게는 500g이하이다.

 

 - 셋째 줄에는 구슬의 개수가 주어진다. 구슬의 개수는 7개 이하이다.

 

 - 넷째 줄에는 확인하고자 하는 구슬의 무게가 자연수로 주어진다.

   구슬의 무게는 40,000 보다 작거나 같은 자연수이다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 추를 가지고 구슬의 무게를 맞추는 문제이다.

 

 - 간단하게 생각해보자면, 추를 놓는 경우는 3가지이다.(왼쪽, 오른쪽, 놓지 않기)

 

 - 즉, 모든 경우를 살펴보게 된다면 $3^30$ 이 되기 때문에 시간안에 불가능해진다.

 

 - 이 문제를 잘 살펴보면 해당 추를 놓아서 만들어질 수 있는 무게는 이전 단계에서 추를 어떻게 놓았는지에 따라 달라진다.

 

 - 다시말해, i번째 추를 놓아서 생기는 무게들은 i-1번째까지 놓아진 무게들에 영향을 받는다.

 

 - i+1번쨰는 i번째 까지의 무게들에 영향을 받는다.

 

 - 이것은 다시 말해 i번째 추를 놓는 경우나 i+1번째 추를 놓는 경우나 결국 i-1번째까지 계산한 결과는 똑같이 이용한다는 것이다.

 

 - 즉, 이 문제는 다이나믹 프로그래밍 문제라는 것을 알 수 있다.

다이나믹 프로그래밍(Dynamic Programming, DP)

 

 - 다이나믹 프로그래밍에서 가장 중요한 것은 점화식을 세우는 것이다.

 

 - 점화식을 세우면, DP[i][j] = DP[i-1][j-w[i]] || DP[i-1][j] || DP[i-1][j+w[i]]가 된다.

 

 - DP[i][j] 에서 i는 i번째 추를 선택하는 경우이고, j는 오른쪽 저울 무게 - 왼쪽 저울 무게 라고 가정한다.

 

 - 즉, j-w[i]는 왼쪽에 i번째 추를 놓는 것이고, j+w[i]는 i번째 추를 오른쪽에 놓는다는 것이다.

 

 - 이 점화식을 이용하여 해당 추를 놓는 모든 경우의 수를 계산하면 된다.

 

 - 주의할 점은 j-w[i]에 의해 배열의 인덱스가 음수가 될 수 있기 때문에 초기 값은 0이 아닌 15501로 설정한다는 것이다.

 

 - 추는 최대 30개, 무게는 500g이기 때문에 15000을 모두 왼쪽에 놓는 경우 -15000이 되기 때문이다.

 

 - 또한, 0부터 시작하는 경우 0-w[i]에 의하여 음수 인덱스가 나올 수 있기 때문에 추 최대 무게인 500부터 살펴보아야한다.

 

 - 시간복잡도의 경우 각 구슬마다 측정하는 것이 아니라 한 번만 측정하면 사용할 수 있기 때문에

   DP배열의 최대 크기인 약 90만이 된다.

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

int weights[31];

int N, w, bN;

bool DP[31][31001];

void findWeights() {
	DP[0][15501] = true;
	DP[0][15501 - weights[0]] = true;
	DP[0][15501 + weights[0]] = true;

	for (int i = 1; i < N; i++) {

		int nowWeight = weights[i];
		
		for (int j = 500; j < 30501; j++) {

			DP[i][j] = DP[i - 1][j-nowWeight] || DP[i-1][j] || DP[i-1][j + nowWeight];

		}

	}

}

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

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

	cin >> bN;
	for (int i = 0; i < bN; i++) {
		cin >> w;

		if (DP[N-1][15501 + w]) {
			cout << "Y ";
		}
		else {
			cout << "N ";
		}

	}


	return 0;
}