(백준/C++) 2629_양팔 저울

2629번: 양팔저울 (acmicpc.net) 문제는 주어진 무게추를 사용하여 만들 수 있는 모든 무게를 찾는 문제입니다.

문제의 그림에서 추와 구슬이 같이 그려져있어 자칫 어렵게 접근할 수도 있지만, 무게추들의 무게들을 전부 받은 후 그 무게추를 이용해서 만들 수 있는 모든 무게를 계산하면 여러 구슬에 대해서도 빠르게 풀어낼 수 있습니다.

무게추는 양쪽 저울에 올릴 수 있으며, 무게추를 사용하지 않을 수도 있습니다. 즉, 무게추를 더해서 무게를 만들수도 있지만, 그렇게 만들어진 무게들에서 무게추를 빼서 무게를 만들수도 있습니다.

접근법

이 문제의 기본적인 접근 방법은 다음과 같습니다.

1. 주어진 무게추들을 하나씩 올려보면서 무게를 계산할 수 있습니다.
2. 이때, 무게추들이 올라간 양팔 저울의 양 쪽에 현재 무게추를 올릴 수 있습니다. 즉, 왼쪽에 무게추를 올릴 수도 있고, 오른쪽에 올릴 수도 있습니다.

1) Tabulation(Bottom-up) 방식

저는 이 문제를 빈 저울에 무게추를 하나씩 올려보는 식으로 생각했습니다.

빈 저울에 무게추를 올릴 때, 왼쪽에 올리던 오른쪽에 올리던 현재 무게추만큼 무게를 잴 수 있습니다.

이후, 두 번째 무게추를 올릴 때, 첫 번째 무게추가 올라간 쪽에 무게추를 올리면 두 무게추를 합한 무게를 잴 수 있습니다.

만약 반대쪽 저울로 현재 무게추를 올린다면, 두 무게추의 차이만큼 무게를 잴 수 있게 됩니다.

부분 문제로 나누기

즉, 이 문제는 작은 문제의 해답을 사용해서 큰 문제의 해답을 구할 수 있습니다.

하나의 무게추를 올린 문제부터 시작해서 모든 무게추를 양팔 저울에 놓는 모든 방법을 구할 수 있습니다.

예를 들어, [1, 2]의 추를 추가할 때, 하나의 무게추를 올린 [1], [2] 의 무게와 두 개의 무게추를 올렸을 때, 같은 쪽에 올리거나 다른 쪽에 올리는 것으로 [3], [1] 의 무게를 잴 수 있습니다.

중복된 부분 문제

이때, 무게추를 추가할 때마다 기존 무게에서 가능한 무게를 계산해야 하므로, 중복된 부분 문제가 발생합니다.

2) 주의 사항

1. 구슬의 무게가 모든 무게추의 합보다 클 수도 있으므로, 이 경우를 고려해야 합니다.
2. 무게추를 왼쪽에 놓거나 오른쪽에 놓을 때, 이번에 계산한 문제가 다음 무게에 대한 계산을 할 때 영향을 끼칠 수 있으므로, 이를 고려해야 합니다.

---

풀이

저는 최대한 메모리 공간이나 시간을 줄이고 싶어서 MAX_W를 가능한 최대 무게로 제한했습니다. 따라서, 주어진 구슬의 무게가 가능한 무게인지 확인하는 과정이 있습니다. (bead <= MAX_W)

또한, if (OutArr[i]) // 현재 무게가 가능하다면 이 부분에서 다음에 계산할 문제에 영향을 주지 않기 위해 결과를 저장하는 또 다른 temp 배열을 사용했습니다.

#include <iostream>
#include <vector>
using namespace std;

void solve(const vector<int>& weights, vector<bool>& OutArr)
{
	OutArr[0] = true;

	// 무게가 작은 추부터 정렬되어 들어있기 때문에 차례대로 가능한 무게들을 채워나간다.
	for(const int& w : weights)
	{
		vector<bool> temp(OutArr); // 현재 상태를 임시로 저장

		for (int i = 0; i < OutArr.size(); i++)
		{
			if (OutArr[i]) // 현재 무게가 가능하다면
			{
				if(i + w < OutArr.size())
					temp[i + w] = true; // 모든 무게추가 같은 쪽에 있는 경우

				if(abs(i - w) >= 0)
					temp[abs(i - w)] = true; // 현재 무게추를 반대쪽에 놓았을 때
			}
		}

		OutArr.swap(temp); // 현재 상태를 저장
	}
}

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

	int N, M, MAX_W = 0;

	cin >> N;
	vector<int> weights(N); // 무게추 초기화
	for (int i = 0; i < N; i++)
	{
		cin >> weights[i];
		MAX_W += weights[i];
	}

	vector<bool> possible(MAX_W + 1, false); // 가능한 무게들을 저장할 벡터
	solve(weights, possible);

	cin >> M;
	while (M--)
	{
		int bead;
		cin >> bead;
		if (bead <= MAX_W && possible[bead])
			cout << "Y ";
		else
			cout << "N ";
	}
}