백준 2437 저울 Java

한 개의 저울이 있고 N개의 저울 추가 있을 때

N개의 저울추를 사용해서 측정할 수 없는 무게의 최솟값을 출력하는 저울 문제이다.

 

이분 탐색으로 풀면 될 것 같다고 생각했지만

그리디 알고리즘으로 분류된 만큼 다른 해법이 있을 거라 생각했다.

 

그리고 어떤 무게에 대해 측정할 수 있는지 없는지를 체크하는 메소드를 어떻게 짤까 고민을

많이 했다. 근데 생각해보면 그리디 알고리즘 문제에서는 대부분 그런 복잡한 과정 없이

생각지도 못한 방법으로 간단히 문제가 풀린다.

이 문제 역시 그런 문제였다.

 

해법은 간단하다.

입력받은 N개의 저울추를 오름차순으로 정렬한 뒤

 

저울이 측정할 수 있는 무게의 최솟값인 1부터

저울추 i번 부터 N번까지를 비교하면 된다.

 

최솟값인 1이 저울추 i번으로 측정 할 수 있다면

최솟값에 저울 추 i번의 무게를 더해준다.

만약 최솟값보다 저울추의 무게가 무거울 경우엔

그 최솟값이 저울 추 N개 측정할 수 있는 가장 작은 값이 된다.

 

예제로 주어진

7

3 1 6 2 7 30 1

을 오름차순으로 정렬하면

1 1 2 3 6 7 30 이 된다.

 

저울로 잴 수 있는 최솟값은 1

저울추[0] = 1이 최솟값 1보다 무겁지 않으므로

최솟값은 2가 된다.

저울추[1] = 1 이 최솟값 2보다 무겁지 않으므로

최솟값은 3이 된다.

저울추[2] = 2  --> 최솟값 5

저울추[3] = 3  --> 최솟값 8

저울추[4] = 6  --> 최솟값 14

저울추[5] = 7  --> 최솟값 21

저울추[6] = 30은 최솟값 21보다 무겁다.

그러므로 저울 추 N개로 측정할 수 있는 최솟값은 21이다.

 

코드는 위 내용과 똑같다.

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] a = new int[n];
        
        for(int i=0; i<n; i++) {
            a[i] = scan.nextInt();
        }
        
        Arrays.sort(a);
        
        int min = 1;
        for(int i=0; i<n; i++) {
            if(min < a[i]) {
                break;
            }
            min += a[i];
        }
        System.out.println(min);
    }

 

어떻게 이러한 방식을 찾아내는지는 모르겠다.

그리고 나중에 알고리즘 분류를 모르고 문제를 풀 때 

어떤 알고리즘으로 해결할지 알아내는 것도 걱정이다.