[Baekjoon Online Judge] 2437번: 저울

2437번: 저울

요구사항

 - 하나의 양팔 저울을 이용하여 물건의 무게를 측정한다. 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 놓을 수 있다.

 

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

입력

 - 첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력

 - 첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

---

 우선 입력받은 저울추의 무게를 오름차순으로 정렬하였다.

 

7
정렬 전 -> 3 1 6 2 7 30 1
정렬 후 -> 1 1 2 3 6 7 30

 

 저울추를 하나씩 추가하여 측정할 수 없는 양의 정수 무게 최소값을 구해본다. 

 

 저울추 1 하나 뿐인 경우 최소값은 2가된다.

 저울추 1이 두 개뿐인 경우 최소값은 3이 된다.

 저울추가 1, 1, 2가 있는 경우 최소값은 4가 된다.

 저울추가 1, 1, 2, 3이 있는 경우 최소값은 8이 된다.

 저울추가 1, 1, 2, 3, 6이 있는 경우 최소값은 14가 된다.

 저울추가 1, 1, 2, 3, 6, 7이 있는 경우 최소값은 21이 된다.

 저울추가 1, 1, 2, 3, 6, 7, 30인 경우 21부터 49까지의 값은 측정할 수 없게 된다. 

 

 즉 21이라는 값은 새롭게 추가된 저울추 30보다 값이 작기 때문에 측정할 수 없는 값 중 가장 작은 값이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Baekjoon2437 {

    public static void main(String[] args) throws IOException {

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

        int n = Integer.parseInt(bufferedReader.readLine());
        List<Integer> weights = new ArrayList<>();

        String[] input = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            weights.add(Integer.parseInt(input[i]));
        }

        Collections.sort(weights); // 오름차순으로 정렬

        int min = 1; // 측정할 수 없는 무게 중 최소값
        for (int i = 0; i < n; i++) {
            if (min < weights.get(i)) break; // 측정할 수 없는 무게 중 최소값 보다 추가된 저울추 무게가 큰 경우
            min += weights.get(i);
        }

        System.out.println(min);

        bufferedReader.close();
    }
}