BOJ 2437 : 저울

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

2437번: 저울

이 문제는 코드는 아주 간단한데 왜 성립되는지 조금 생각해야 하는 문제이다.

일단 추를 정렬하자.

1부터 i까지의 합을 sum이라고 하자. (1<=i<=n)

sum에 추로 1부터 sum까지 모두 표현 가능하다는 가정을 할 것이다.

a[i]값이 sum의 값보다 작으면 다른 추를 이용해서 sum까지의 수를 다 표현할 수 있기에 sum의 가정을 만족한다.

하지만 a[i]값이 sum의 값보다 크면 sum과 a[i]사이의 값은 존재하지 않음을 알 수 있다. 

그러므로 O(n)만에 그런 값을 찾으면 끝.

#include <bits/stdc++.h>
#define MEM 1004
#define sanic ios_base::sync_with_stdio(0)
#define f first
#define s second
#define pb push_back
#define all(x) ((x).begin()),((x).end())
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9+7;
ll t,n;
ll a[MEM];
int main() {
    sanic; cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> a[i];
    sort(a,a+n);
    ll sum=0;
    for(int i=0; i<n; i++){
        if(sum+1<a[i]) break;
        sum += a[i];
    }
    cout << sum+1;
}