[CSES] Missing Coin Sum

https://cses.fi/problemset/task/2183/

문제

You have n coins with positive integer values. What is the smallest sum you cannot create using a subset of the coins?
Input
The first line has an integer n: the number of coins.
The second line has n integers x_1,x_2,\dots,x_n: the value of each coin.
Output
Print one integer: the smallest coin sum.
Constraints

1 <= n <= 2 * 10^5
1 <= x_i <= 10^9

Example
Input:
5
2 9 1 2 7

Output:
6

풀이

n개의 코인과 그 값이 주어졌을 때 코인을 이용해서 만들 수 없는 가장 작은 값을 찾는 문제이다.

n개의 정수를 이용해 k를 만들 수 있는지 확인하는 방법을 생각해봤을 때, 두가지 방법이 있다.

• 모든 조합을 직접 확인 -> O(2^n)
• DP를 활용 -> O(n*k)

DP를 활용해서 최적화한다고 해도 이 문제에서 k는 1부터 계속 증가하기 때문에, 계산량이 매우 많아진다.

조금 더 효율적인 방식이 필요한데, two pointer를 이용해 특정 구간값을 유지하고, 포인터를 증가시키는 방식으로 확인해보는 방법은 코인의 부분집합이 연속적이라는 조건이 없기 때문에 불가능하다.

그럼 실제로 모든 조합을 확인하는 게 아니라, i번째 코인까지 사용했을 때 특정 수 k까지는 모두 만들 수 있음을 보장한다면?

i+1번째 코인을 추가했을 때는 k + v[i+1] 까지 만들 수 있음이 보장된다.

예를 들어, 1, 2, 2, 7, 9 인 경우 첫번째 숫자부터 확인하면

• 1로 만둘 수 있는 수 -> 1
• 1, 2를 사용해 만들 수 있는 수 -> 1, 2, 3(1+2)
• 1, 2, 2를 사용해 만들 수 있는 수 -> 1, 2, 3, 4(2+2), 5(3+2)

즉 i-1번째 수를 활용하면 k까지 만들 수 있다는 것은
1, 2, .. , k 까지의 조합은 이미 가능하다는 것이므로 i번째 수를 사용하면 1+v[i] ~ k+v[i]까지는 만들 수 있다는 의미이다.

이때 만약 v[i] > k+1 이라면, k+1은 만들 수 없는 수가 된다.

이 논리가 충족되려면 배열이 정렬된 상태여야 한다.

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<ll> v;
    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        v.push_back(a);
    }

    sort(v.begin(), v.end());
    
    ll now = 0; //현재 만들 수 있는 값 
    for (int i = 0; i < n; i++) {
        if(v[i]>now+1)
            break;
        else {
            now += v[i];
        }
    }
    cout << now+1;
    return 0;
}