[C++] 백준 BOJ 2437번 저울

문제에서 측정할 수 없는 양의 정수 무게 중 최솟값을 요구하고 있다. 

그러므로 측정 가능한 양의 정수 무게를 작은 무게부터 만들어보자.

 

그러기 위해서는 먼저 주어진 추를 오름차순 정렬하자. 

문제의 예시를 빌리자면 추의 무게를 오름차순 정렬하여 [1, 1, 2, 3, 6, 7, 30] 이라는 배열을 얻을 수 있다. 

 

가장 작은 무게의 추 1을 사용하여 만들 수 있는 무게를 다음과 같이 {추} : {만들 수 있는 무게}로 표현하자.

{1} : {1}

이제 사용하는 추를 1무게짜리 하나 더 추가한다면 이렇게 표현된다. 

{1, 1} : {1, 2}

계속 추가해보면..

{1, 1, 2} : {1, 2, 3, 4}  ->  {1, 1, 2, 3} : {1, 2, 3, 4, 5, 6, 7}  ->  {1, 1, 2, 3, 6} : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}....

으로 생각해볼 수 있다. 

 

잠시

{1, 1, 2, 3} : {1, 2, 3, 4, 5, 6, 7}  ->  {1, 1, 2, 3, 6} : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}

을 자세히 관찰해보면

 

추 1, 1, 2, 3으로 이미 무게 7까지는 어떻게든 만들어낼 수 있다.

그다음 무게인 8부터 13까지의 무게는 다음과 같이 생각하면 된다!

무게 8은 (추 1, 1, 2, 3으로 무게 2를 만드는 방법)+무게 6인 추로 만들어질 수 있다.

무게 9은 (추 1, 1, 2, 3으로 무게 3을 만드는 방법)+무게 6인 추로 만들어질 수 있다.

무게 10은 (추 1, 1, 2, 3으로 무게 4를 만드는 방법)+무게 6인 추로 만들어질 수 있다.......

이렇게 무게 13까지 계속 만들 수 있는 것이다. 

 

어떤 추의 집합 S가 무게 1부터 k까지 만들 수 있다고 가정하자.

추의 집합에 추가될 추의 무게가 w라면, 

k+1<w가 아니라면, 추가된 이후의 추의 집합은 무게 1부터 k+w까지 만들 수 있다. 

 

단, k+1<w 이라면 무게 1부터 k까지 만들 수 있겠지만, 무게 k+1은 만들 수 없게 된다. 

{1, 1, 2, 3, 6, 7} : {1 에서 20} -> {1, 1, 2, 3, 6, 7, 30} : {1에서 20, 31에서 50} 이 되는 것을 관찰하면 이해하기 쉽다. 

 

#include <iostream>
#include <algorithm>
using namespace std;
int N;
int scales[1001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N;
    for(int i=0;i<N;i++)
        cin>>scales[i];
    sort(scales, scales+N); //먼저 추를 오름차순으로 정렬
    
    int possibleMax=0; //추의 집합이 만들 수 있는 최대 무게
    for(int i=0;i<N;i++){
    	//scales[i]가 추의 집합에 추가된다. 
        if(possibleMax+1<scales[i])
            break;
        else
            possibleMax+=scales[i];
    }
    cout<<possibleMax+1;
    return 0;
}

이렇게 되면 추를 정렬하는데 O(nlogn)의 시간복잡도, 추의 집합에 추를 하나씩 추가하는데 O(n)의 시간복잡도로

총 시간복잡도는 $$O(nlogn)$$으로 해결