[BOJ] 2473. 저울

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

접근 방법

아이디어만 있다면 풀 수 있는 문제이다.

물론... 그 기발한 아이디어가 없어서 질문 검색을 통해 그 아이디어를 얻게 되었다.

아이디어는 이러하다.

---

먼저 n번째 까지의 누적값을 Sn 이라 해보자.

그리고 배열에서 n번째 값을 An 이라 하자.

그리고 S(n-1) 보다 만약 (An)-1값이 크면 S(n-1) ~ A(n-1) 의 값은 만들지 못한다.

따라서 만들 수 없는 최솟값은 S(n-1) 이 된다.

---

내가 생각하는 증명은 이러하다.

Sn은 1부터 시작할 것이다.

왜냐하면 첫번째 원소가 2라면 제일 최솟값인 1을 만들지 못하기 때문이다.

그럼 이제 차근차근 값들이 더 해가지면서 만들 수 있는 조합들이 무수하게 많아질 것이다.

하지만 Sn이란 n까지의 숫자들 중 최대로 만들 수 있는 값이다.

그런데 그 (다음 값-1)이 바로 최댓값보다 크다면 그 다음 수를 만들지 못 할 것이기 때문에 이런식으로 빠르게 구할 수 있다.

Ex) 1, 2, 5

2번째 까지 누적값은 3이다.

그 다음 3번째를 보려고 했더니 누적값 보다 크다고 한다.

그럼 3번째 값으로 가기 전에 먼저 , 4의 값을 만들 수 있을지 봐보자.

누적값이 3이다. 근데 여기서 어떠한 수를 고른다한들 이미 최대인데 고를 수 있겠는가?

불가능하다. 그렇기 때문에 만들 수 없는 최솟값은 4가 된다.

Need Know

1. 그리디
2. 배열 안에 있으면 그 합 들 중에서 가장 작은 수를 구하는 방법..?

전체 코드 ( Java )

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N;
    static int[] scale_weights;
    public static void main(String[] args) throws IOException {
        set();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }

    static void set() throws IOException {
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        scale_weights = new int[N];
        for(int i=0; i<N; i++){
            scale_weights[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(scale_weights);
    }
    static void solve() throws IOException {
        int sum = 1;
        for(int i=0; i<N; i++){
            if(sum < scale_weights[i]) break;

            sum += scale_weights[i];
        }
        bw.write((sum) + "");
    }
}