[백준] 2437: 저울 - JAVA

in Algorithm on 그리디 알고리즘

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

풀이

저울추들을 이용하여 무게를 측정하는데 측정할 수 없는 최소값을 구하는 문제이다.

방법이 안떠올라서 정답을 찾아봤다…

먼저 추의 무게들을 정렬하여 작은 것부터 꺼낸다.

올리려는 저울추의 무게가 지금까지 올린 무게의 합 + 1 보다 크다면 무게의합+1이 최소값이 된다.

올린 무게의 합을 sum이라고하면 이는 1~sum까지 무게를 측정할 수 있다는 말이다.

sum = 5인 상태에서 다음 저울추가 6이라면 sum + 6까지 무게를 잴수있다. 하지만 다음 저울추의 무게가 7이라면 sum + 1인 6이 측정할 수 없는 최소값이 된다.

메모리: 14384KB

시간: 136ms

언어: Java 11

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] weight = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            weight[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(weight);

        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (weight[i] > sum + 1) {
                break;
            }
            sum += weight[i];
        }

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

}