[백준/C++/KOI] 2437번 저울 증명 및 풀이

---

문제를 처음 읽었을 때 dp라는 생각이 스쳐지나갔는데 100만개의 저울추가 1000까지의 숫자를 가지면 배열로 만들 수 없을만큼 큰 수가 되니 포기하고 1초라면 1억번 연산이니 최대 N log N 일 것이라고 생각하였다.

sorting 한 번으로 구할 수 있다는 소리인데...

 

도저히 그리디로 풀 방법이 떠오르지 않아 질문 게시판의 도움을 얻으니 배열에서 다음에 오는 숫자가 기존 숫자들의 합보다 작으면 다음에 오는 숫자까지 더한 값까지 모든 수를 나타낼 수 있다 라는 힌트를 얻었고 이를 증명하고자 한다.

 

Prove

• S(k) = ∑a[k] 이고 S(K)는 1 ~ S(K)까지 모든 수를 표현할 수 있을 때, S(k) + a[k+1]는 S[k] + a[k+1]까지 모든 수를 표현할 수 있다.

Basis

• S(1) = a[1] = 1 일 때  a[1]까지 모든 수를 표현 할 수 있다.

Assume

• S(k) 일 때 1 ~ S(k)까지 모든 수를 표현할 수 있다

Recursion Step

• S(2) = S(1) + a[2] 일 때, a[2]는 {1, 2}를 원소로 지닐 수 있다.
  a[2]가 1일 때 S(1) + a[2]까지 모든 수는 subset of S(1) + a[2]로 표현할 수 있다.
  a[2]가 2일 때 모든 수는 subset of S(1) + a[2]로 표현할 수 있다.
  
  같은 방법으로S(k)일 때까지 모든 수를 표현할 수 있다고 가정한다면
  
  
• S(k+1) = S(k) + a[k+1]는 (단 a[k+1] <= S(k+1))
  1 <= a[k+1] <= S(k) 이며 S(k)는 1~S(k)까지의 모든 수를 표현할 수 있으므로
  1 ~ S(k) + a[k+1]로  S(k) + a[k+1]까지 모든 수를 표현할 수 있다.

따라서 a[k+1]이 S(k)보다 작거나 같고 S(k)까지의 모든 수를 표현할 수 있다고 할 때
모든 곳에서 S(k) + a[k+1]는 모든 수를 표현할 수 있다.

그렇다면 다음에 오는 a[k+1]이 S(k) + 1 보다 큰 숫자라면 S(k) + 1이 표현할 수 없는 가장 큰 숫자일 것이다.
( S(k)는 S(k)까지가 최대로 표현할 수 있는 숫자이고 S(k)+1을 표현할 수 없으므로)

---

#include <bits/stdc++.h>
using namespace std ;
int N, S ;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0) ;
    cin >> N ;
    vector<int> vec(N) ;
    
    for(int &it : vec)
        cin >> it ;
    
    sort(vec.begin(), vec.end()) ;

    for(auto it : vec)
    {
        if(it > S + 1) break ;
        else S += it ;
    }
    
    cout << S + 1 ; 
}

---

느낀점: 이런 문제에 대한 알고리즘 설계를 어떻게 보자마자 할 수 있을까... 라는 생각이 들었다.

저 논리가 된다는 것을 이해하는데도 엄청나게 오랜 시간이 걸렸는데ㅎ PS 문제를 많이 풀면 늘 수 있는 부분일까 하는 생각이 들었다.

문제링크: https://www.acmicpc.net/problem/2437

2437번: 저울