[백준] 2437번 저울

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define long long size_t
using namespace std;

int N;
int arr[1000];

int main(){
    cin>>N;
    for(int i=0; i<N; i++){
        cin>>arr[i];
    }
    sort(arr,arr+N);
    
    int res = 1;
    for(int i=0; i<N; i++){
        if(arr[i]>res){
            break;
        }
        res+=arr[i];
    }
    cout<<res;
}

[풀이]

res: 지금까지 만들 수 있는 모든 연속적인 (자연수의 범위의 끝 + 1) 이다.

arr[i]가 res보다 작거나 같으면 → 이 수를 써서 기존 만들 수 있는 범위를 더 확장할 수 있음

그런데 arr[i] > res가 되는 순간 → 이 수로는 res 자체를 만들 수 없으니, 그게 바로 만들 수 없는 가장 작은 수임

[참고]

https://algosu.tistory.com/11