백준 2437 - 저울

문제 설명

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 무게추로 만들 수 없는 최소한의 무게를 구하면 된다.

 

해당 문제는 dp로 푼다면 간단하게 풀 수 있다.

유명한 냅색 문제와 동일하기 때문이다.

하지만, 냅색 문제와 동일하게 푼다면 메모리 초과가 발생한다.

이를 우회하기 위해 dp배열을 1차원으로 만들고 표현가능한 무게를 임시로 저장한 뒤 나중에 추가하게 된다면 시간 초과가 발생한다.

따라서 접근법을 변경해야 한다.

 

냅색 문제는 자신 이전의 무게추로 만들 수 있는 무게에 자신을 포함하여 만들 수 있는 무게를 늘려나간다.

이와 유사하게 해당 문제를 풀 수 있다.

추가 무게순으로 정렬되어 있다면 만들 수 있는 무게의 구간을 정할 수 있다.

예를 들어 보자.

무게 추가 [1, 1, 2, 3, 9]이라고 가정해 보자.

1은 첫 번째 무게추를 사용하여 만들 수 있다.

2는 첫 번째 무게추에 두 번째 무게추를 추가하여 만들 수 있다.

3을 만드는 경우를 살펴보면 현재까지 1~2의 수는 모두 만들 수 있고 세 번째 무게추를 추가한다면 1~4의 구간을 만들 수 있게 된다.

이렇게 만들 수 있는 수의 연속된 범위를 늘려 나가다 보면 8을 만드는 경우에서 예외가 발생한다.

마지막 무게추를 추가하기 전에는 1~7까지의 모든 수를 만들 수 있었다. (1+1+2+3 = 7)

거기에 마지막 무게추인 9를 더하려 했더니 추가될 구간이 9~16이 된다.(9, 1+9 ~ 7+9)

즉, 이전까지 만들 수 있던 영역의 최댓값이 현재 사용하려는 무게추의 무게보다 작다면 만들지 못하는 수가 생긴다는 뜻이다.

문제의 조건에 의해 만들 수 없는 무게는 양의 정수로 한정되어 있기 때문에 1에서 시작하여 계산한다면 더욱 쉽게 구할 수 있다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<int> weights;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;

	cin >> N;
	weights.resize(N);

	for (int i = 0; i < N; i++)
	{
		cin >> weights[i];
	}

	sort(weights.begin(), weights.end());

	int res = 1;
	for (int i = 0; i < N; i++) 
	{
		if (weights[i] > res) break;
		res += weights[i];
	}

	cout << res;
	
	return 0;
}

---