[백준] 2437번. 저울(JAVA)

문제

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

---

풀이(12분)

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

public class Main {

    // 오름차순으로 정렬해서 빼내자.
    // 최댓값을 구성할 수 있다는거는 거기까지는 전부 만들 수 있다는 소리이다.
    // 예를 들어, 이전 최댓값이 4였고, 다음 값이 4여서 최대 8이 된다고 치자.
    // 그럼 1,2,3,4가 전부 있었다는 소리이기 때문에 5,6,7도 자동으로 구성되고 8까지 가능해진다.

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        List<Integer> list = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < n; i++){
            list.add(Integer.parseInt(st.nextToken()));
        }

        Collections.sort(list);

        int nowMax = 1;
        for(int i : list){
            if(nowMax < i){
                System.out.println(nowMax);
                return;
            }
            nowMax += i;
        }
        System.out.println(nowMax);
    }

}

---

문제 풀이 전략

 

주석에 작성된 것이 전부이다.

 

주석에 작성된 예를 다시 생각해 보자.

1. 숫자를 오름차순 정렬하여 하나씩 뽑아낸다.
2. 이를 누적합으로 정리하며, 최댓값을 추적한다.
3. 새로 나온 값이 누적합의 값을 초과한다면 끝난다.

어떻게 보면 너무나도 간단한 규칙이다. 왜 이렇게 구성될까?

• 3, 1, 6, 2, 7, 30, 1이라는 입력값으로 생각해 보자.
• 정렬하면 1, 1, 2, 3, 6, 7, 30 이 된다.
  • 앞에서부터 뽑으며 누적합을 추적하자.
  • 1단계 : 1
  • 2단계 : 2
  • 3단계 : 4
  • 4단계 : 7

이 규칙을 정리하면 다음과 같다.

3단계부터 살펴보자. 2 -> 3으로 넘어갈 때 뽑은 숫자는 2이다. 그렇기에 2단계의 2와 더해 4를 만족시킨다.

그럼 3은?이라는 생각이 들겠지만 2단계에 2가 가능했다는 것은 이미 1~2가 모두 존재한다는 소리이기에 만족시킬 수 있는 것이다.