2437번 저울

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

오름차순까지 생각을 했지만, 그 후 막혔었다.

이런 Greedy 문제를 더 많이 풀어야겠다.

[input]

7

3 1 6 2 7 30 1

[output]

21

[오름차순 결과]

1

1

2

3

6

7

30

예를 들어, 임의의 무게 w에 대하여, 1 ~ w까지 측정 가능하다고 가정하자.

여기에 무게가 x인 추가 더 있었다고 한다면, 1 ~ w + x까지 측정이 가능하다.

하지만, x + 2 이상인 추가 주어질 때는 w + x + 1을 측정할 수 없게 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
vector<int> v;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    scanf("%d", &n);
    
    int input;
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &input);
        v.push_back(input);
    }
 
    sort(v.begin(), v.end());
 
    if (v[0] != 1) {
        printf("1\n");
    }
    else {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (v[i] > sum + 1) {
                // 여기서 출력하면 안 된다.
                // 1 1 입력시 아무것도 출력을 하지 않는다.
                break;
            }
            sum += v[i];
        }
        printf("%d\n", sum + 1);
    }
 
    return 0;
}