[백준] 2629번: 양팔저울

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

2629번: 양팔저울

---

가능 여부를 확인해서 해결하는 dp 문제다.

 

1. 문제 조건

1) 양팔 저울의 왼쪽에 구슬이 있는데, 주어진 추를 사용해서 구슬의 무게를 잰다.

2) 추와 구슬의 무게가 주어졌을 때, 그 구슬의 무게를 잴 수 있는지 여부를 출력한다.

3) 추는 왼쪽 또는 오른쪽에 올릴 수 있다.

4) 추를 올리지 않을 수도 있다.

5) 추의 개수는 최대 30, 무게는 최대 500 이하의 자연수다.

 

2. dp 배열 정의

추의 사용 여부와 올리는 위치에 따라

다양한 경우가 생겨나서 조금 생각하기 어려웠다.

 

추를 주어진 순서대로 번호를 매겼을 때

어떤 특정한 무게를 만들 수 있는지 여부를 dp 배열로 저장하면 된다.

#define MAXN 31
#define MAXW 15001	// 30 X 500

// dp[n][w] = n번째 추까지 왔을 때 w를 만들 수 있다면 true, 아니라면 false
int dp[MAXN][MAXW];

// weight[n] = n번째 추의 무게
int weight[MAXN];

 

3. 해결법

추의 사용 조건을 생각하면 총 3가지 경우가 나온다.

구슬은 항상 왼쪽에 있다고 가정한다.

 

1) 추를 사용하지 않는다.

2) 추를 오른쪽에 올린다.

3) 추를 왼쪽(구슬)에 올린다.

 

위 3가지 경우에 대해 재귀 함수를 사용해서

DFS 방식으로 dp 배열을 만들면 된다.

 

1) N < n (base)

- 현재 확인하는 n번째 추가 전체 추의 개수보다 크면 재귀함수를 끝낸다.

2) dp[n][w] == true (base)

- 현재 확인하는 n번째 추까지 만들 수 있는 무게가 이미 가능하다고 기록되어 있다면, 재귀함수를 끝낸다.

3) 그 외

- 재귀함수 안에 들어왔으니 무게 w를 만들 수 있다. 따라서 dp[n][w] = true 로 기록한다.

- 추를 사용하지 않는 경우, 무게를 변화시키지 않고 재귀함수를 호출한다.

- 추를 오른쪽에 올리는 경우, 현재 무게에 weight[n] 을 더해서 재귀함수를 호출한다.

- 추를 왼쪽에 올리는 경우, 현재 무게에 weight[n] 를 뺀 값의 절댓값으로 재귀함수를 호출한다.

 

재귀함수를 호출할 때는 당연히 n을 1 증가시켜서 인자로 넘겨주어야 한다.

왜냐하면 다음 추를 본다는 뜻이기 때문이다.

 

추를 오른쪽에 올리면, 내가 측정할 구슬의 무게가 더 늘어나게 된다.

따라서 현재 무게에 weight[n] 을 더해서 재귀호출의 인자로 넘겨준다.

 

추를 왼쪽에 올리면, 실질적으로 내가 측정할 구슬의 무게가 줄어들게 된다.

따라서 현재 무게에 weight[n] 을 뺀 값을 재귀호출의 인자로 넘겨주어야 한다.

그런데 weight[n] 을 뺀 결과가 음수가 나올 수 있다.

이 때는 단순히 지금까지 올려 놓은 추의 위치를 서로 바꾸어준다고 생각하면 된다.

따라서 현재 무게에 weight[n] 을 뺀 값의 절댓값을 재취호출의 인자로 넘겨주어야 한다.

 

코드로 보면 다음과 같다.

void solve(int n, int w) {
	if(n > N || dp[n][w]) return;	// 사용 가능한 추 개수를 넘거나 이미 결정난 경우

	dp[n][w] = true;

	solve(n+1, w);					// 1) 추를 올리지 않는 경우
	solve(n+1, w + weight[n]);		// 2) 추를 오른쪽에 올리는 경우
	solve(n+1, abs(w - weight[n]));	// 3) 추를 왼쪽에 올리는 경우
}

---

전체 풀이 코드는 다음과 같다.

#include <iostream>
using namespace std;

#define MAXN 31
#define MAXW 15001

bool dp[MAXN][MAXW];
int weight[MAXN];

int N;

inline int abs(int n) { return (n > 0) ? n : -n; }

void solve(int n, int w) {
	if(n > N || dp[n][w]) return;

	dp[n][w] = true;

	solve(n+1, w);
	solve(n+1, w + weight[n]);
	solve(n+1, abs(w - weight[n]));
}

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

	cin >> N;
	for(int i=0; i<N; i++) cin >> weight[i];

	solve(0, 0);

	int T; cin >> T;
	while(T--) {
		int w; cin >> w;

		if(w >= MAXW) cout << "N ";
		else		  cout << (dp[N][w] ? "Y " : "N ");
	}

	return 0;
}