[백준 Gold 3] 2437 저울 -Java

문제링크 : https://www.acmicpc.net/problem/2437

2437번: 저울

 

접근 과정 : 

• 처음에는 감이 오지 않아서,  추의 무게 조합을 모두 구해볼까 생각도 했다.
• 그런데 잴 수 없는 최소 무게는 항상 1부터 시작하더라..
• 그러면, 추를 무게순으로 정렬시켜 놓고 -> 앞에것부터 더해가면 유의미한 현상이 보이지 않을까 생각했다.
• 좀 더 생각을 해보니, 누적합보다 현재 인덱스의 추의 무게가 더 크면 그 누적합을 측정할 수 없다!!
• 그리고 1부터 시작하니, 누적합보다 작은 수는 어떻게든 측정할 수 있더라.!!!!

 

소스 코드 및 결과 :

package BOJ;

/* 
    저울
*/

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

public class BOJ2437 {
    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] num = new int[N];

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

        int weight = 1;

        for (int i = 0; i < N; i++) {
            if (weight < num[i]) {
                break;
            }
            weight += num[i];
        }

        System.out.println(weight);
    }

}

 

 

P.S 

그리디 알고리즘은 정말 생각 한끗차이로 갈리는 것 같다..

문제에 맞게 여러가지 다양한 방법으로 생각을 해야한다.

그래서 재밌는 거겠지.