[백준 2437] 저울

문제

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

 

알고리즘

Greedy

 

풀이

$N$개의 저울이 주어졌을 때, 잴 수 없는 무게의 최솟값을 구하는 문제입니다.

 

기존에 잴 수 있는 구간이 [0,R] 일 때, 새로운 추 A가 새로이 등장하면 새롭게 잴 수 있는 구간은 [A,A+R] 일 것입니다. 만일 R+1>=A 라면 이 구간은 [0,A+R]로 통합되어 잴 수 있는 구간이 새로이 갱신되겠지만 아니라면 답은 R+1입니다.

즉, 추의 무게를 정렬한 후 R과 추가할 추 A의 무게를 계속해서 비교해주면 됩니다. R은 잴 수 있는 무게의 최댓값이므로 지금까지의 추의 무게의 총합입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector<int> vt(N);
    rep(i, N) cin >> vt[i];
    sort(vt.begin(), vt.end());
    int sum = 0;
    bool temp = false;
    rep(i, N) {
        if (sum + 1 < vt[i]) {
            temp = true;
            cout << sum + 1;
            break;
        }
        sum += vt[i];
    }
    if (!temp) cout << sum + 1;
    return 0;
}