[KOI] 백준 2437 - 저울

www.acmicpc.net/problem/2437

 

예제에 주어진 추들을 정렬하고 무게들을 더하다 보면 무게가 30인 추를 넣을 때 지금까지 더한 무게 20과 거기에 30을 더한 무게 50 사이의 무게를 만들 방법이 없어 답은 21이 되는 것을 관찰할 수 있다.

 

즉 정렬된 추들의 무게를 누적 합으로 저장하면서 현재 추가할 추의 무게가 누적 합 범위 안에 들어온다면 누적합에서 현재 추를 더한 범위 내의 무게를 만들 수 있다고 생각할 수 있다.

 

그렇지 않다면, 즉 추가할 추의 무게가 누적 합 + 1 범위를 벗어난다면 답은 지금까지 더한 누적 합 + 1이 된다.

 

왜 누적 합 + 1이냐면 추가할 추의 무게가 누적 합 + 1일 경우 누적 합 + 1은 추가할 추 한개로 무게를 잴 수 있기 때문에 그보다 큰 범위를 고려하도록 한다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
int ar[1000];
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> ar[i];
    
    int sum = 0;
    sort(ar, ar + n);
    
    if (ar[0] != 1)
    {
        cout << 1;
        return 0;
    }
    sum = ar[0];
 
    for (int i = 1; i < n; ++i)
    {
        if (sum + 1 < ar[i])
        {
            cout << sum + 1;
            return 0;
        }
        sum += ar[i];
    }
 
    cout << sum + 1;
}