백준2437 저울

작성일 | In

문제 링크

  • http://icpc.me/2437

문제 출처

  • 2011 전국 본선 초등3

사용 알고리즘

  • 그리디

시간복잡도

  • O(n log n)

풀이

3 1 6 2 7 30 1이 입력으로 들어온다고 가정을 해봅시다.
오름차순으로 정렬을 하면 1 1 2 3 6 7 30 이 되겠죠.

첫 번째 원소인 1을 봅시다. 이 숫자로는 1을 만들 수 있습니다.
첫 번째부터 두 번째까지의 원소를 봅시다. 1과 1을 이용해서 1과 2를 만든 수 있습니다.
세 번째 원소까지 봅시다. 1, 1, 2를 이용해서 1부터 4까지의 모든 수를 만들 수 있습니다. 네 번째 원소까지 이용한다면 7, 다섯 번째 원소까지 이용한다면 13, 여섯 번째 원소까지 이용한다면 20을 만들 수 있습니다. 그러나 일곱 번째 원소까지 모두 이용한다고 해도 21을 만들지는 못합니다. 이제 이것을 어떻게 찾는지 알아봅시다.

정렬을 한 뒤 누적합을 먼저 구할겁니다. 1 2 4 7 13 20 50이 되겠죠.
만약 i-1번째까지의 누적합이 (i번째 원소-1)보다 작다고 해봅시다. i-1까지의 누적합이 x라고 한다면 첫 번째 원소부터 i-1번째의 수를 더해서 만들 수 있는 최대의 숫자가 x라는 것은 쉽게 알 수 있습니다. 만약 (i번째 원소-1)이 x보다 크다면 x와 i번째 원소 사이에 있는 모든 수를 만들지 못합니다.

이 원리를 이용하여 문제를 그리디 방식으로 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<int> v(n+1);
    vector<int> s(n+1);
    for(int i=1; i<=n; i++) cin >> v[i];
    sort(v.begin()+1, v.end());
    if(v[1] > 1){
        cout << 1;
        return 0;
    }
    for(int i=1; i<=n; i++){
        s[i] = v[i] + s[i-1];
        if(s[i-1]+1 < v[i]){
            cout << s[i-1]+1;
            return 0;
        }
    }
    cout << s[n]+1;
}