[백준] 2437. 저울

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

2437번: 저울

 

 

이 문제의 핵심은 무게들의 합으로 만들 수 없는 무게들 중 가장 작은 값을 원한다는 것이다. 즉, 굳이 모든 무게들의 조합을 구하지 않아도 됨을 암시하고 있다.

 

작은 무게들의 조합부터 따져야하기 때문에 무게를 기준으로 추들을 먼저 정렬하자.

 

먼저 누적합으로 접근해보자. 0번째 추부터 k번째 추까지 만들 수 있는 무게의 조합들을 0부터 k까지의 합으로 알 수 있을까?

 

그럼 0번째 추의 무게가 1, 1번째 추의 무게가 2라고 해보자. 이 추들로는 무게를 1부터 3까지 만들 수 있다. 이는 0~1번째 추들의 무게합과 같다. 2번째 추의 무게가 2라면 1~5까지 만들 수 있으며, 3이라면 1~6까지 만들 수 있다. 0~k까지의 무게 누적합이 모든 조합을 나타내고 있음을 알 수 있다.

하지만 추의 무게와 상관없이 항상 성립하지 않는다. 2번째 추의 무게가 5라고 하면, 4를 만들 수 없기 때문이다. 

 

패턴을 보면 알 수 있듯, k+1번째에 오는 추가 k번째까지 누적된 무게의 합보다 2이상 무겁다면 얄짤없이 (k번째까지의 누적합 + 1)이 답이된다. k+1번째 추의 무게가 (k번째까지의 누적합 + 1) 보다 같거나 작아야지만 (k번째까지의 누적합 + 1)을 만들 수 있기 때문이다.

 

즉, k+1번째 추의 무게가 (k번째까지의 누적합 + 1) 보다 같거나 작아야지 1~( [k]번째 누적합 + [k+1]번째 추의 무게)까지의 조합이 가능하다.

 

만약 위 명제가 거짓이 되려면 k+2 ~ N번째 추들 중, k+1번째 추보다 무게가 작은 추가 존재해야한다. 하지만 추들을 무게를 기준으로 오름차순 정렬해놨기 때문에 k+1번째보다 가벼운 추는 존재할 수가 없으므로 위 명제가 참이 된다.

 

따라서 추들의 무게를 순회하면서 현재 누적된 무게의 합보다 보고있는 추의 무게가 2이상 크다면, 누적된 무게 + 1이 답이된다. 만약 추의 무게가 (누적된 무게의 합 + 1) 이하라면 해당 추의 무게를 누적시키면 된다.

 

다음은 코드이다.

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

int w[1000];
int N;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	
	for(int i=0; i<N; i++) cin >> w[i];
	sort(w, w+N);
	
	int sum = 0;
	for(int i=0; i<N; i++) {
		if(w[i] > sum + 1) break;
		sum += w[i];
	}
	
	cout << sum + 1 << "\n";
}