[백준 2437] 저울 - JAVA

문제

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

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

예를 들어,
무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때,
이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.

입력

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

출력

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

---

접근 방법

처음에는 DP 혹은 조합을 생각했지만
시간 복잡도나 무게의 범위로 보나 사용하지 못할 것이라 판단했습니다.

그래서 수학적으로 생각했을 때 이 문제를 해결할 수 있을 것이라고 생각했고
그리디로 문제를 해결할 수 있었습니다.

• 입력 받은 저울들의 무게를 오름차순으로 정렬합니다.
• $for$문을 통해 저울추의 무게 배열인 $W$를 순회합니다.
  • 현재 선택한 무게 추$(w)$가 현재까지 만들 수 있는 숫자의 연속$(S) + 1$보다 작거나 같은지를 확인합니다.
    • 작거나 같다면 무게를 S에 누적합니다.
    • 그렇지 않다면 반복문을 종료하고 정답을 $S+1$로 출력합니다.

이런 로직이 어떻게 될 수 있는지를 생각해보면
현재까지 만들 수 있는 숫자의 연속을 $S$라고 한다면
그 다음 숫자인 $S+1$은 반드시 만들지 못한다는 것을 의미합니다.

그렇기 때문에 만약 다음 무게 추가 $S+1$보다 큰 수가 온다면
당연하게도 $S+1$이라는 숫자는 무게추의 조합으로 만들 수 없는 수가 됩니다.

그러므로 $W$를 순회하면서 현재의 $w$가 $S+1$보다 큰 값이 아니라면
연속성이 보장되고 현재 무게인 $w$를 제외한 저울로 $S$라는 숫자까지 연속성을 유지했기 때문에
$w$를 포함하는 $S$의 값이 $w$만큼 증가하게 됩니다.

예시

현재 무게추 $K$개로 숫자 100까지 연속적으로 측정할 수 있었습니다.
그렇다면 현재까지의 $S = 100$
다음에 오는 추의 무게가 $w = 101$이라 가정했을 때
이 $w$하나로 $101$이라는 무게를 측정 가능하기 때문에
우선 $101$까지 연속성을 보장받고
$1$부터 $100$까지 모든 숫자를 만들 수 있었기 때문에
위의 연속성에 101이라는 무게추만 추가한다면
$100 + 101 = 201$까지 연속적으로 만들 수 있음을 보장합니다.

아이디어를 고안하는 것에 난이도가 있으므로 코드 자체는 간단하게 구현할 수 있었습니다.

---

코드

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

public class Main {
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] W = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            W[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(W);

        System.out.println(greedy(W));
    }

    
    static long greedy (int[] W) {
        long S = 0;

        for (int w : W) {
            if (w > S + 1) break;
            S += w;
        }

        return S + 1;
    }
}