[백준 / JAVA] 2437번 저울

문제

https://www.acmicpc.net/problem/2437

접근

이렇게 내용이 간단한 문제 오랜만에 보는 것 같다.
근데 어려움;

조합으로 모든 경우의 수를 체크 하는 건 시간 초과로 불가능하다.
$\binom{1000}{1} + \binom{1000}{2} + \binom{1000}{3} + ... + \binom{1000}{1000}$

정렬을 해서 가장 작은 값부터 어떻게 하면 될 것 같은데 도저히 생각이 나질 않아 풀이를 참고했다.

측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 것이기 때문에, 1부터 값을 늘려가며 측정할 수 없는 무게가 나왔을 때 그 무게가 정답이 될 것이다.

측정하고 싶은 정수를 target이라고 하자.

주어진 추들을 오름차순으로 정렬하고, 가장 작은 무게부터 하나씩 추가해가면, target보다 큰 추를 처음 만나는 순간 target이 측정할 수 없는 가장 작은 무게가 된다.

이게 무슨 말인가...
문제의 예시를 보자.
무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 있다.
오름차순 정렬을 하면 1, 1, 2, 3, 6, 7, 30.

1. 초기 상태에서 0개의 추로 측정할 수 있는 무게는 0이다.
   그렇다면 target은 1일 것이다.
2. 정렬된 저울추에서 가장 왼쪽, 무게가 1인 추로 target을 측정할 수 있다.
   그렇다면 현재 측정 가능한 무게의 범위는 [0 ~ 1]이 된다.
   target += 1. 즉, 다음 target 값은 2.
3. 다음, 무게가 1인 추로 target을 측정할 수 있다.
   그렇다면 현재 측정 가능한 무게의 범위는 [0 ~ 2]이 된다.
   target += 1. 즉, 다음 target 값은 3.
4. 다음, 무게가 2인 추로 target을 측정할 수 있다.
   그렇다면 현재 측정 가능한 무게의 범위는 [0 ~ 4]이 된다.
   target += 2. 즉, 다음 target 값은 5.
   ...

이 과정을 반복하다 보면 target이 21일 때, 추의 무게가 30이므로 측정이 불가능 하여 답을 구할 수 있다.

---

4번의 과정이 이해가 안 될 수 있다.

3번에서 측정 가능한 무게의 범위는 [0 ~ 2]이다.
즉, 0, 1, 2의 무게가 측정 가능하다는 말이다.
그렇다면, 무게가 2인 추를 추가했을 때 측정 가능한 무게의 범위는 [0 ~ 4]가 될 것이다.

풀이

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));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(arr);

        int target = 1;
        for (int element : arr) {
            if (element > target) break;

            target += element;
        }

        System.out.println(target);
    }
}

정리

오히려 이렇게 간단한 문제가 어려울 때가 있다.
메인 아이디어를 다양한 방향으로 유연하게 생각하는 것이 중요해 보인다.