백준 2437번 저울 C++

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

 

i-1까지의 누적합이 i번째 원소와 같거나 1 작은경우는 무조건 만들 수 있다. i-1까지의 누적합이 i번째 원소의 값보다 2 이상 작으면 i번째 원소는 만들 수 없다. 여기까지는 완벽하게 이해가 됐는데

 

i번째 원소의 값이 누적합보다 작은 경우에 무조건 만들수 있다는 것은 와닿기는 하는데 완벽하게 이해가 되지는 않는 것 같다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

#include <bitset>

using namespace std;
using int64 = long long;

int n;
vector<int> v;

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

    cin >> n;
    v = vector<int>(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());

    int ans = 1;
    int sum = 1;
    bool _break = false;

    if (v[0] == 1) {
        for (int i = 1; i < n; i++) {
            if (sum + 1 < v[i]) {
                ans = sum + 1;
                _break = true;
                break;
            }
            sum += v[i];
        }
        if (!_break) ans = sum + 1;
    }
    cout << ans;
}