2437_저울_그리디 알고리즘

문제

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

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

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

입력

  첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력

  첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

---

문제 해결

  이 문제는 이 많은 경우의 수를 어떻게 해야할지에 대해 고민이였다. 하지만 이문제의 해결법은 바로 누적합을 이용한 공식이다.

 

(i - 1까지의 원소의 누적합 + 1 >= i번째 원소) 이 공식이 성립하면 i - 1까지의 원소의 누적합 ~ i 까지의 원소의 누적합 사이의 값은 모두 만들 수 있다는 의미를 포함한다. 그러므로 저 공식이 틀리게 되면 누적합 + 1이 최솟값이 되는 것이다.

 

#include <iostream>
#include <algorithm>
#define MAX 1001

using namespace std;

int n;
int weight[MAX];
int sum = 1;

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> weight[i];
	}
	sort(weight + 1, weight + n + 1);
	for(int i = 1; i <= n; i++) {
		if(weight[i] > sum) {
			break;
		}
		sum += weight[i];
	}
	cout << sum << endl;
	return 0;
}