[Baekjoon] 2629번: 양팔저울

 

 

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

2629번: 양팔저울

 

---

 

문제 해결 과정

착안

추의 갯수가 $n$개일 때, 각각의 추를 사용하거나 사용하지 않고 무게를 만들 수 있는 경우의 수를 모두 계산하면 지수 시간($=O(2^n)$)의 시간 복잡도를 가지므로 동적계획법(dynamic programming)을 활용하여 문제를 해결하고자 하였다.

 

추가 하나씩 새로 주어질 때마다, 기존에 잴 수 있던 무게와 더불어 추가적으로 잴 수 있는 무게들은 다음과 같다.

• 새로 추가된 추 하나 만큼의 무게를 잴 수 있다.
• 기존에 가지고 있던 추의 조합으로 만들 수 있는 무게에 새로운 추의 무게를 더한 만큼 무게를 잴 수 있다.
• 기존에 가지고 있던 추의 조합으로 만들 수 있는 무게와 새로운 추의 무게 사이의 차만큼을 잴 수 있다.

 

구현

$i$ 번째 단계의 추가 새로 주어졌을 때, 이전 단계 ($i-1$ 개의 추를 사용)에서 측정 가능했던 무게들에 대해

• 새로 추가된 추 하나의 무게
• 이전 단계에서 만들었던 무게 + 새로 추가된 추의 무게
• 이전 단계에서 만들었던 무게와 새로 추가된 추의 무게 사이의 차

를 추가적으로 측정할 수 있다. 이때 동적계획법을 활용하기 위해 1차원 배열을 선언한 다음, 반복문을 통해 위와 같은 계산하려고 하면 새로 측정 가능해지는 무게들이 계속 추가됨으로 인해 다음 계산에 영향을 주어 자칫하면 잘못된 결과를 산출하기 십상이다. 따라서 이 부분만 해결하면서 위의 계산들을 수행하면 문제를 해결할 수 있다.

 

 

1) 2차원 배열을 활용한 동적계획법

가장 기본적인 해결 방법으로는 2차원 배열 DP[$i$][$j$]를 선언하여, 구슬을 사용하는 갯수 $i$에 따라 만들 수 있는 무게 $j$를 동적계획법을 통해 계산하는 것이다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

bool marbles[31][40001];

int main()
{
	int n;
	cin >> n;
	
	marbles[0][0] = true;
	for (int i = 1; i <= n; i++)
	{
		int weight;
		cin >> weight;

		for (int j = 0; j < 40001; j++)
		{
			if (marbles[i - 1][j])
			{
				marbles[i][j] = true;
				marbles[i][j + weight] = true;
				marbles[i][weight - j >= 0 ? weight - j : j - weight] = true;
			}
		}
	}

	int m;
	cin >> m;
	while (m--)
	{
		int marble;
		cin >> marble;
		cout << (marbles[n][marble] ? "Y" : "N") << " ";
	}

	cout << "\n";
	return 0;
}

 

 

2) 1차원 배열을 활용한 동적계획법

무게를 계산하는 방식의 특성상 1차원 배열 그대로 사용해도 문제를 해결할 수 있다. 단, 계산 순서와 반복문 내의 루프 제어 방향에 따라 전혀 의도치 않은 결과가 나올 수 있기 때문에 이러한 점에 유의해야 한다.

 

무게가 $w_i$인 $i$ 번째 추가 주어질 때마다, 측정 가능한 무게 $j$를 표시할 배열 DP[$j$]에 대해

• 배열의 마지막 요소부터 인덱스가 감소하는 방향으로 DP[$j$]가 true이면 DP[$j+w_i$]를 true로 만든다.
• 배열의 처음 요소부터 인덱스가 증가하는 방향으로 DP[$j$]가 true이면 DP[$\vert j-w_i \vert$]를 true로 만든다.

 

위의 순서대로 계산을 수행하면 주어진 $n$개의 모든 추에 대해 계산했을 때 정확한 결과를 얻을 수 있다.

* 기존의 무게에 새로운 추의 무게를 더한 값(윗줄)부터 먼저 계산한 다음, 무게의 차만큼(아랫줄)을 계산해야 한다.

 

[스포 주의] 풀이 2) 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
using namespace std;

bool marbles[40001];

int main()
{
	int n;
	cin >> n;

	marbles[0] = true;
	int sum = 0;
	while (n--)
	{
		int w;
		cin >> w;

		sum += w;
		for (int i = sum; i >= 0; i--)
			if (marbles[i])
				marbles[i + w] = true;

		for (int i = 0; i <= sum; i++)
			if (marbles[i])
				marbles[w - i >= 0 ? w - i : i - w] = true;
	}

	int m;
	cin >> m;
	while (m--)
	{
		int marble;
		cin >> marble;
		cout << (marbles[marble] ? "Y" : "N") << " ";
	}

	cout << "\n";
	return 0;
}

 

실행 결과

2차원 배열을 활용한 동적계획법

 

1차원 배열을 활용한 동적계획법