[백준] 2437번: 저울 (Java)

1 . 문제 설명

양팔 저울 - 한쪽에는 저울추만 놓을 수 있고, 다른 쪽에는 물건만 올려놓을 수 있다.

N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구한다.

ex) 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추 → 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21

• 저울추 개수: 1 ≤ N ≤ 1,000
• 각 추의 무게: 1 ≤ W ≤ 1,000,000

 

• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

• 만약 1부터 n까지의 모든 정수 무게를 만들 수 있다면, 다음으로 만들 수 있는 무게는 n+1 이 된다. 이 원리를 사용하여여 문제를 해결할 수 있다.
• 저울추의 무게들을 오름차순으로 정렬한다.
  • 작은 무게부터 차례대로 탐색하여 만들 수 있는 무게의 범위를 확장한다.
• 그리디 알고리즘 → 정렬된 저울추를 차례대로 탐색하며, 현재까지 만들 수 있는 무게의 합을 갱신한다.
  • 만약 현재까지 1부터 S까지의 모든 무게를 만들 수 있다고 가정하고, 다음으로 정렬된 저울추 무게가 w 일 때
  • $w ≤ S + 1$
    • 1부터 S까지의 모든 무게에 w를 더한 무게(즉, w+1,…,w+S)와 w 자체를 만들 수 있다.
    • 1…S 와 w, w+1, … w+S 가 합쳐져서 1 … S+w 의 모든 무게를 연속적으로 만들 수 있게 된다.
  • $w>S+1$
    • w를 사용하지 않고서는 S+1의 무게를 만들 수 없다.
    • 따라서, S+1이 만들 수 없는 가장 작은 양의 정수 무게가 된다.
  • 이 과정을 반복하며, 현재까지 만들 수 있는 무게의 합을 갱신한다.

 

최종 접근 방식

• 저울추의 무게들을 오름차순으로 정렬한다. (weight)
• 현재까지 만들 수 있는 무게의 합을 저장할 변수(sum)을 선언하고, 초기값을 0으로 설정한다.
• 정렬된 저울추 배열(weight)을 순회한다.
  • 각 저울추 무게를 w라고 할 때,
    • w ≤ sum + 1이면 sum += w로 갱신한다.
    • w > sum + 1이면 sum + 1이 만들 수 없는 가장 작은 무게이므로 반복문을 종료하고 sum + 1을 출력한다.
  • 모든 저울추를 순회했다면,
    • sum + 1이 만들 수 없는 가장 작은 무게이므로 반복문을 종료하고 sum + 1을 출력한다.

 

3. 최종 코드

package lsj.study.algorithm_note.Greedy;

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

public class Main {

    static int N; // 저울추 개수
    static int[] weight; // 저울추 무게
    static int sum = 0; // 저울추 무게 합

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        weight = new int[N];
        String[] weights = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            weight[i] = Integer.parseInt(weights[i]);
        }

        Arrays.sort(weight); // 오름차순 정렬
        for (int i = 0; i < N; i++) { // 저울추 순회
            if (weight[i] <= sum + 1)
                sum += weight[i]; // 무게 합 갱신
            else if (weight[i] > sum + 1) {
                System.out.println(sum + 1); // 만들 수 없는 가장 작은 무게
                return; // 종료
            }
        }

        System.out.println(sum + 1); // 만들 수 없는 가장 작은 무게
    }
}

시간복잡도

`O(N log N)` (정렬)

 

4. 분석 및 참고사항

• 측정할 수 없는 가장 작은 수를 찾는 것이므로 조건에 만족하는 첫 경우에서 멈추는 게 중요
• 완전 탐색이 불가능 해 보일 경우 그리디를 후보군에 올릴 필요가 있음 ( 만약 메모리와 시간이 무한하면 완전탐색도 가능하지만 그게 불가능하기 때문에, 적은 범위만 탐색하는 방법을 떠올려야 함 )
• 보통 완전탐색이 아닌 탐색 문제에서, 최솟값, 최댓값이 등장하면 그리디일 확률이 높음