[백준 2437 : JAVA] 저울 / 그리디

문제

---

 

 

 

풀이

---

이 문제는 수학적인 규칙을 찾아야 풀 수 있는 문제다.

{1, 2, 3,       <---- 다음에 어떤 수가 와야 추로 측정할 수 없는 최소 무게가 될까?

 

답은 8이다. 8이 오면 측정할 수 없는 최소 무게로 7이 된다.

 

{1, 2,      <---- 다음에 어떤 수가 와야 추로 측정할 수 없는 최소 무게가 될까?

 

답은 5이다. 5가 오면 측정할 수 없는 최소 무게로 4이 된다.

 

{1,      <---- 다음에 어떤 수가 와야 추로 측정할 수 없는 최소 무게가 될까?

 

답은 3이다. 3이 오면 측정할 수 없는 최소 무게로 3이 된다.

 

규칙이 보이는가?

{1, 2} 가 있을 때 이 추들로 만들 수 있는 수는 각각의 수인 1과 2, 그리고 이 둘의 합인 3이 된다. 오름차순으로 정렬되어 있다는 가정 하에,  이것을 일반화해보면 첫 번째 원소인 1부터 ~ 1부터 마지막 원소까지의 합까지의 수는 만들 수 있는 수가 된다. 즉, 1부터 마지막 원소까지의 합 + 1한 수가 다음 원소로 나오지 않으면 그 수는 만들 수 없다는 얘기가 된다.

 

 

 

코드

---

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

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N;
    private static int[] arr;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        Arrays.sort(arr);

        int sum = 0;
        for (int i = 0; i < N; i++) {
            if (sum + 1 < arr[i]) {
                break;
            }
            sum += arr[i];
        }

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