[Baekjoon,2437] 저울

처음에는 모든 수의 조합을 만들어 찾으려 했으나 중량의 최대 합이 10억이어서 이는 포기했다. 그래서 어떻게 해결할지 고민하던 중 주어진 수열을 정렬해보니 방법이 떠올랐다.

해결

주어진 중량들을 오름차순으로 정렬한 뒤 앞에서 부터 수를 하나씩 더해나간다. 이때 현재까지 합해진 수 보다 다음 수가 더 큰데 여기에 공백이 생기면 (현재 합해진 수+1)가 만들 수 없는 수가 되는 것이다. 즉, 현재까지 합해진 수와 다음 수를 이용한 조합으로 더 이상 (현재 합해진 수+1)를 조합할 수 없는 것이다.

예를 들어 예제로 주어진 입력을 보자.

7
3 1 6 2 7 30 1

이를 정렬하면 아래와 같이 될 것이다. 여기서 하나씩 끝까지 더해나가며 공백이 생기는 부분을 찾아보자.

1 1 2 3 6 7 30 

2 2 3 6 7 30 

4 3 6 7 30 

7 6 7 30

13 7 30

// 공백 발생!!!
20 30 

공백이 발생하게 된 20까지는 조합이 가능하나 21은 조합이 불가능 하므로 답은 21이 되는 것이다.

구현

이를 코드로 구현하면 아래와 같다. 구현 시 모든 조합이 만들어 질 수 있는 경우를 고려해야 한다. 이때는 (모든 수의 합+1)을 출력하면 된다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N=1001;
const int MAX_W=1000000001;

int n;
int w[MAX_N];

int main()
{
    cin>>n;
    for(int i=0;i<n;++i)
        scanf("%d",&w[i]);
    sort(w,w+n);
    
    int sum=0;
    bool ok=true;
    for(int i=0;i<n;++i)
    {
        if(sum+1<w[i])
        {
            cout<<sum+1<<endl;
            ok=false;
            break;
        }
        sum+=w[i];
    }
    if(ok)
        cout<<sum+1<<endl;

    return 0;
}