key points

• 양의 정수인 N개의 저울 추를 입력받음
• 입력 받은 수들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값

Solution

예제로 문제를 접근해보자면, N=7 이므로 7개의 무게를 입력받는데, "3 1 6 2 7 30 1" 이 숫자들로 측정할 수 없는 양의 정수 무제 중에 최솟값을 구하는 것이다.

1, 2, 3, 4(1+1+2), 5(2+3), 6, 7, 8(2+6)... 이렇게 하다보면 20(1+1+2+3+6+7)까지 가능하다. 그래서 21이 측정할 수 없는 양의 정수 무게 중에 최솟값이 된다.

그런데 더 세련된 풀이 방법을 찾았다.

입력받은 저울 추의 무게는 [ 3 1 6 2 7 30 1 ]
오름 차순으로 정렬하면, [ 1 1 2 3 6 7 30 ]

저울추[0] = 1 로 측정할 수 없는 최솟값은 2이다.
저울추[0] = 1 과 저울추[1] = 1 로 측정할 수 없는 최솟값은 3이다. 즉, 최솟값은 이전의 저울 추 무게(저울추[0])로 측정할 수 없는 최솟값 + 저울추[1] 값이 된다.
저울추[2] = 2 --> 최솟값 5
저울추[3] = 3 --> 최솟값 8
저울추[4] = 6 --> 최솟값 14
저울추[5] = 7 --> 최솟값 21
저울추[6] = 30은 최솟값 21보다 무겁다.
그러므로 저울 추 N개로 측정할 수 있는 최솟값은 21이다.

# Code

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        /* Input */
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] array = new int[N];

        for (int i = 0; i < N; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(array);

        /* Output */
        int min = 1;
        for (int i = 0; i < N; i++) {
            if (min < array[i]) break;
            min += array[i];
        }

        System.out.println(min);

        br.close();
    }
}

Result

System.out.println 으로 한게 시간도 메모리도 조금 작게 나왔다. 늘 궁금한거지만... bw.write와 System.out.println 의 성능 차이가 궁금하다 :)