[백준 온라인 저지] 2437. 저울

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

 

1. 입력

- 첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다.

- 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

 

2. 출력

- 첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

 

3. 예제

 

4. 코드

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        int[] chu = new int[n];
        StringTokenizer token = new StringTokenizer(br.readLine());
        for(int i=0 ; i<n ; i++)
            chu[i] = Integer.valueOf(token.nextToken());
        Arrays.sort(chu);
        int mass = 1;
        for(int i=0 ; i<n ; i++){
            if(mass<chu[i]) break;
            mass += chu[i];
        }
        System.out.print(mass);
    }
}

- 14372KB, 136ms

- 위 예시에서 추가 [1,1,2,3,6,7,30]이 있는데, 추를 앞에서부터 하나씩 추가하면서 잴 수 있는 무게를 써보면 다음과 같다.

[1] -> 1
[1,1] -> 1, 2
    // [1]로 만들 수 있는 무게에 새로 추가한 1을 가지고 만들 수 있는 무게는 2
[1,1,2] -> 1, 2, 3, 4 
    // [1,1]로 만들 수 있는 무게에 새로 추가한 2를 가지고 만들 수 있는 무게는 3, 4
[1,1,2,3] -> 1, 2, 3, 4, 5, 6, 7
    // [1,1,2,3]으로 만들 수 있는 무게에 새로 추가한 3을 가지고 만들 수 있는 무게는 5, 6, 7

- 예시를 보면 알 수 있듯이, 추를 오름차순으로 정렬했을 때 sum=1+chu[0]+chu[1]+...+chu[i] < chu[i+1]이라면 주어진 추로는 sum을 만들 수 없음이 보장된다. 그래서 오름차순으로 정렬한 후 chu[0]이 1이 아니면 잴 수 없는 최소 무게가 1이 된다.