[Greedy] BOJ 2437 저울

문제 링크 : www.acmicpc.net/problem/2437

2437번: 저울

주어진 무게추로 측정할 수 없는 최소무게를 구하는 문제이다.

무게추 1, 2, 3을 갖고 있다고 가정할 때, 우리는 1에서 6까지의 모든 무게를 측정할 수 있다.

이 상태에서 새로운 무게추 5가 추가되었을 때, 이미 우리는 1에서 6까지의 무게를 1~3 무게추로 측정할 수 있었기 때문에 각 무게에 대한 무게추 조합에 5 무게추만 추가한 새로운 조합을 만들어 낼 수 있다.

다시 말해 우리가 2, 3 무게추를 이용해 5의 무게를 측정할 수 있다면, 이 조합에 5 무게추만 추가해 5 + 5 = 10 의 무게를 측정할 수 있다는 것이다. 따라서 측정할 수 있는 무게의 범위는 1 ~ 11이 된다.

 

하지만 만약 1, 2, 3 무게추를 갖고 있을 때 새로운 무게추 8이 추가된다면 어떻게 될까?

1, 2, 3 무게추로 측정할 수 있는 최대 무게는 6이지만, 1, 2, 3 새 무게추 8을 더해 측정할 수 있는 최소 무게는 8이기 때문에 우리는 7의 무게를 측정할 수 없게 된다.

이를 통해 다음 사실을 알 수 있다.

"현재까지 측정 가능한 최대 무게 + 1보다 큰 무게추가 추가된다면 측정할 수 없는 무게가 발생한다."

따라서 주어진 무게추들을 오름차순으로 정렬한 후, 앞까지의 누적합보다 2 이상 큰 무게추가 등장했을 경우가 답이 된다.

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
typedef pair<int, int> p;
 
int n;
vector<int> weight;
 
int greedy() {
    int sum = weight[0];
    if (sum > 1) return 1;
 
    for (int i = 1; i < weight.size(); i++) {
        if (weight[i] > sum + 1) return sum + 1;
        sum += weight[i];
    }
 
    return sum + 1;
}
 
void init() {
    int w;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> w;
        weight.push_back(w);
    }
    sort(weight.begin(), weight.end());
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    int answer = greedy();
 
    printf("%d\n", answer);
 
    return 0;
}