[BaekJoon] 2437 저울 (Java)

1.  문제 링크

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

2.  문제

요약

• 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 저울의 한 쪽에는 저울추들만, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있습니다.
• 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 양의 정수인 저울추의 개수를 나타내는 N이 주어지고 두 번째 줄에 1보다 크거나 같고 1,000,000보다 작거나 같은 저울추의 무게를 나타내는 N개의 양의 정수가 주어집니다.
• 출력: 첫 번째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    // 추는 오름차순으로 정렬
    // 추[0] ~ 추[n - 1]까지의 합을 m이라고 할 때, 1 ~ m 사이의 무게는 추[0] ~ 추[n - 1]로 표현 가능하다
    //      -> 1이 있어야 가능!
    //      -> 1이 없다면 1이 표현이 불가능한 것도 있지만 1 ~ m 사이의 모든 무게를 표현하려면 1이 필요!
    // 1. 추[n] <= m + 1 -> 추[0] ~ 추[n]을 이용해 1 ~ (m + 추[n])의 무게를 표현 가능하다
    //      -> 추[0] ~ 추[n - 1]을 이용해 m이라는 무게까지는 모두 표현할 수 있기에 다음에 나오는 무게가 m + 1 이하여야 이어지는 수가 될 수 있음
    // 2. 추[n] > m + 1 -> 추[0] ~ 추[n]을 이용해 m + 1의 무게는 표현이 불가능
    
    static int N;
    static int[] weights;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        weights = new int[N];

        for(int idx = 0; idx < N; idx++) weights[idx] = scanner.nextInt();
    }

    static void solution() {
        Arrays.sort(weights);

        if(weights[0] != 1) {
            System.out.println(1);
            return;
        }

        int sum = 0;
        for(int idx = 0; idx < N; idx++) {
            if(weights[idx] <= sum + 1) sum += weights[idx];
            else break;
        }

        System.out.println((sum + 1));
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 주어진 추의 무게들을 weights라는 배열에 넣고 오름차순으로 정렬합니다.
• weights[0]부터 weights[N - 1]까지의 합을 M이라고 한다면, 추의 무게에 1이 있다는 전제 하에 1부터 M 사이의 무게는 weights[0]부터 weights[N - 1]로 표현이 가능합니다.
• 1이 존재하지 않는다면 가장 작은 양의 정수인 1부터 표현이 불가능하므로 1이 답이 됩니다.
• 만약 1이 존재한다면 모든 추들을 확인하면서 다음 2가지를 확인합니다.
  1. weights[N] <= M + 1
     • weights[0]부터 weights[N - 1]을 이용하여 M이라는 무게까지는 모두 표현할 수 있기 때문에 다음에 나오는 추의 무게가 (M + 1) 이하이어야지만 이어지는 수가 될 수 있습니다.
  2. weights[N] > M + 1
     • weights[0]부터 weights[N - 1]을 이용하여 M이라는 무게까지는 모두 표현할 수 있기 때문에 다음에 나오는 추의 무게가 (M + 1) 이하이어야지만 이어지는 수가 될 수 있습니다.
       • 그런데 다음에 나오는 추의 무게가 (M + 1)보다 크기 때문에 (M + 1)의 무게는 표현할 수 없습니다.
• 위 방법을 이용하여 첫 번째 추부터 하나씩 추의 무게를 더해가면서 현재 추의 무게가 (이전까지의 모든 추의 무게의 합 + 1)보다 작거나 같은지 확인하여 만약 현재 추의 무게가 더 커지는 경우가 발생한다면 (이전까지의 모든 추의 무게의 합 + 1)이 답이 됩니다.