[백준 2629] 양팔저울

다이나믹 프로그래밍 문제

www.acmicpc.net/problem/2629

www.acmicpc.net/problem/5557

위 문제와 접근 방식이 비슷하므로 위 문제를 먼저 해결할 것을 권장합니다.

---

[문제 풀이]

 

추가 N개 주어져 있을 때, 각 구슬에 대해 양팔저울의 수평을 맞출 수 있는가에 대한 문제입니다.

굳이 모든 추를 사용하지 않아도 되고, 구슬과 추의 위치에 대한 제한은 없습니다.

 

추의 개수가 30이고, 구슬의 개수가 7개이므로 제한이 작아 보입니다.

 

지금부터 구슬은 무조건 왼쪽으로 고정시킨다고 생각하겠습니다.

수평을 맞춰야 하므로 오른쪽에 추를 올리는 경우는 왼쪽의 무게를 -시키는 과정이라 생각할 수 있고 왼쪽에 추를 올리는 경우는 당연히 왼쪽의 무게를 +시키는 과정이라 생각할 수 있습니다.

그리고 구슬을 고정하였으므로 추가 주어진다는 것은 구슬의 무게에서 추의 무게를 더하고 빼는 과정이라고 생각할 수 있습니다.

 

이제 브루트포스의 시간 복잡도를 구해보자면, 모든 추에 대해 더하고 빼는 작업이 가능하므로 추의 개수 N에 대해 $2^N$만큼의 시간이 걸리고, 구슬의 개수가 M개 있을 경우 $O(2^NM)$가 됩니다.

말도 안되는 시간 복잡도가 나왔습니다. 브루트 포스로는 절대 풀 수 없습니다.

 

주목해야 할 가장 첫 번째는 구슬의 무게가 최대 7번뿐이지만 계속 바뀐다는 것입니다.

즉, 구슬의 정보에 대해 입력을 받기 전 미리 dp테이블을 구현하는 것이 좋아 보입니다.

 

그리고 가장 주목해야 할 점인 문제를 푸는 핵심 아이디어는 구슬 무게 제한이 40000이 최대이며 자연수라는 것입니다.

크기가 40000인 dp테이블을 생성하고 주어진 추의 무게를 사용하여 가능한 구슬의 무게를 dp테이블에 기록하는 것이 모든 구슬에 대응하기도 좋고 시간 복잡도도 좋아 보입니다.

 

추가 N개가 있고 구슬의 무게 제한을 W라 할 때, N개까지 추를 사용하여 W사이의 구슬의 무게만큼을 만들 수 있는지에 대한 dp테이블의 크기는 $N \times W$만으로 충분해 보이고, 시간 복잡도 역시 $O(NW)$로 가능할 것 같습니다.

그리고 구슬의 무게에 대해 수평을 맞출 수 있을지에 대한 것은 dp테이블의 인덱스만 조사하면 되므로 $O(1)$에 가능합니다.

 

시간 복잡도가 매우 개편되었습니다. 이제 위의 로직대로 예제에 대한 테이블을 작성해 나가면서 점화식을 찾아보겠습니다.

dp문제는 늘 로직을 떠올리는 부분이 난관이라 위처럼 로직을 떠올리기만 한다면 코딩은 금방 가능합니다.

 

 

 

dp테이블을 2차원으로 선언합니다.

그리고 행 i는 사용하는 추의 개수, 열 j는 구슬의 무게로 두고 테이블을 구성하겠습니다.

 

dp[0][0] = 1로 설정

편의를 위해 dp[0][0] = 1로 설정하였습니다.

 

 

추를 한개만 사용

무게가 1인 첫번째 추를 사용한 결과입니다.

당연히 구슬의 무게가 1인 경우만 수평이 맞춰집니다. 그러므로 dp[1][1] = true로 놓겠습니다.

 

 

모든 추를 사용

이게 예제의 최종적인 dp테이블의 단편입니다. 편의를 위해 열을 4로 설정하였습니다. 

예제는 구슬의 무게가 최대 3이지만 실제 테이블은 구슬의 무게가 몇으로 들어올지 모르므로 열이 40000까지 있어야 합니다. 

그러므로 실제로는 dp[2][5] 역시 1로 설정되어 있습니다.

 

 

점화식을 만드는 첫 번째 과정으로는, 모든 추를 사용할 필요가 없다고 하였으므로 dp[i - 1][j]가 1이면 dp[i][j]역시 무조건 1입니다.

 

그리고 i-1개의 추를 사용하는 과정 이후 현재의 추에서 더하고 빼는 것을 사용하여 구슬의 무게를 맞춘다 하였으므로 dp[i - 1][j - w]와 dp[i - 1][j + w]가 1인지 확인하는 것으로 dp[i][j]가 1인지 0인지를 확인할 수 있습니다.

 

문제는 j + w가 40000보다 클 수 있다는 점과 j - w가 음수가 될 수 있는 점입니다.

j + w가 40000보다 큰 경우는 무시해도 됩니다. 추의 무게가 40000보다 커질 수 있었다면 그렇지 않겠지만 다행히 추의 무게를 다 합쳐도 15000에 불과합니다.

그러나 j - w가 음수가 된다는 것은 왼쪽의 무게가 오른쪽의 무게보다 커졌다는 의미이고, 우리는 양팔 저울의 추의 위치를 서로 바꿀 수 있으므로 j - w가 음수가 됐다면 절댓값을 씌워주는 방식으로 대처해야 합니다.

 

즉, 정리하자면 dp[i][j] = dp[i - 1][j] || dp[i - 1][|j - w|] || dp[i - 1][j + w] 입니다.

 

위와 같이 $O(NW)$의 시간 복잡도로 문제를 해결할 수 있습니다.

 

---

[소스 코드] / C++

 

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

bool isIn(int n) {
	return n < 40001 ? true : false;
}

int Abs(int n) {
	return n < 0 ? -n : n;
}

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

	int N;
	cin >> N;

	vector<vector<bool>> dist(N + 1);
	vector<bool> temp(40001, false);
	dist[0] = temp;
	dist[0][0] = true;

	for (int i = 1; i < N + 1; i++) {
		vector<bool> temp(40001, false);
		dist[i] = temp;
		dist[i][0] = true;

		int w;
		cin >> w;
		for (int j = 0; j < 40001; j++) {
			dist[i][j] = dist[i - 1][j] || dist[i - 1][Abs(j - w)];
			if (j + w < 40001) dist[i][j] = dist[i][j] || dist[i - 1][j + w];
		}
	}

	int Q;
	cin >> Q;

	while (Q--) {
		int M;
		cin >> M;

		if (dist[N][M]) cout << 'Y' << ' ';
		else cout << 'N' << ' ';
	}

	return 0;
}