[BOJ] 2437. 저울

[작성일]

• 2022-02-28

[분류]

• 누적합
  
  
  

[문제링크]

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

[요구사항]

• 주어진 저울추들로 잴 수 없는 최소 값을 구하라.
  
  
  

[풀이]

우선 처음에 보자마자 숫자를 오름차순으로 정렬하고 작은 수부터 봐야겠다는 생각이 들었다. 현재까지의 수를 모두 더한 수가 저울로 잴 수 있는 최대 수라는 생각이 들었고 그 다음에 오는 수를 또 더해서 잴 수 있는 최대값을 구해야했다.
그렇게 생각했을 때 그 다음 오는 수가 누적합 + 1보다 크면 결국 그 사이의 숫자는 잴 수 없기 때문에 그 때의 누적합 + 1이 최종 정답이 된다는 결론에 도달했다.
그대로 코드로 구현했다.

[코드]

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Long> list = new ArrayList<>();
        while (st.hasMoreTokens()) {
            list.add(Long.parseLong(st.nextToken()));
        }

        // 추를 오름차순으로 소팅
        Collections.sort(list);

        // 다음 원소가 누적합 + 1보다 큰 경우에는 누적합 + 1을 만들 수 없기 때문에 바로 답이된다.
        long sum = 0;
        for (long i : list) {
            if (sum + 1 < i) {
                System.out.println(sum + 1);
                return;
            }
            sum += i;
        }
        System.out.println(sum + 1);
    }
}