# 2629. 양팔저울

관련 알고리즘 : DP, 배낭(Knapsack), 재귀

 

문제 링크 : https://www.acmicpc.net/problem/2629

2629번: 양팔저울

---

해결 과정

 

문제에서 주어졌던 예제를 통해 생각해보면,

1g, 4g짜리 추 2개가 주어진 경우 잴 수 있는 구슬의 무게는

1. 1g과 4g을 같이 놓았을 때 무게 = 5g
2. 1g과 구슬의 무게 = 4g일 때, 구슬의 무게 =  4g - 1g = 3g
3. 추를 한개만 놓았을 경우, 각 1g과 4g

이렇게 3가지 경우로 나눌 수 있다.

 

정리하면,

1. 구슬과 함께 놓기 ( 구슬과 추를 합친 무게가 다른 추의 무게가 되는 경우)
2. 구슬의 반대편 저울에 놓기 ( 구슬의 무게 = 추 하나 혹은 여러개의 추를 합친 무게가 되는 경우)
3. 양팔 저울에 놓지 않기 ( 해당 추가 사용되지 않는 경우)

위의 3가지 경우에서 구할 수 있는 무게 중 구슬의 무게가 있다면, 주어진 추를 이용하여 구슬의 무게를 잴 수 있다는 것을 의미하게 된다.

주어진 추를 이용하여 잴 수 있는 무게를 완전 탐색을 이용하여 탐색하면 추의 개수는 최대 30개이므로 최대 3^30의 경우가 존재하게 되기 때문에 시간 초과가 발생한다.  그런데 양팔 저울에 추를 올리고 빼고, 반대편 접시로 이동하는 이 문제와 같은 경우, 현재 추를 처리하는 것이 이전에 내가 추를 어디에 놓았는가에 영향을 받기 때문에 DP를 사용한다.

 

DP를 사용하기 때문에 이중 배열을 통해 각 3가지 경우에 대한 점화식을 세워 보면,

• dp[i][j] = i번 추 까지 사용했을 시, j 무게 측정 가능 여부
• dp[i+1][j+w[i]] = 추를 추가하는 경우
• dp[i+1][j-w[i]] =  추를 덜어내거나/ 구슬과 같은 쪽에 놓는 경우
• dp[i+1][j] = 추를 양팔 저울에 놓지 않는 경우

위의 식들을 이용해 재귀함수를 만들어 문제를 해결할 수 있었다.

 

---

C++ 코드

 

// BOJ 2629. 양팔저울

#include <iostream>
#include <cmath>

using namespace std;

int n; // 추의 개수
int b; // 구슬 개수
int bw; // 구슬 무게
int w[31]; // 추의 무게 저장 배열
int dp[31][40001]; // dp[i][j] 꼴

void InputN() // 추 입력 받기
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> w[i];
	}
}

void Solve(int i, int j) 
{
	if (i > n || dp[i][j])
		return;

	dp[i][j] = true;

	Solve(i + 1, j + w[i]);
	Solve(i + 1, j - w[i]);
	Solve(i + 1, j);
}

void Output() // 구슬 무게 확인 가능 여부 출력함수
{
	cin >> b;

	for (int i = 0; i < b; i++)
	{
		cin >> bw;

		if (bw > 15000) // 최대 추 무게의 합보다 구슬 무게가 클 때 측정불가
			cout << "N ";
		else if (dp[n][bw]) // 구슬 무게 확인 가능 시(true일 시)
			cout << "Y ";
		else
			cout << "N "; // 구슬 무게 확인 불가능(false)
	}
}

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

	InputN();
	Solve(0, 0);
	Output();
}