문제 설명
하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.
무게가 양의 정수인 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;
}