저울

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

풀이

입력받은 추들의 무게의 모든 경우의 수를 구한다면 O(n!)일 것이다.

이는 시간이 엄청나게 걸린다는 것이고 정답을 구하기에는 너무 효율적이지 못한 알고리즘이라는 것은 당연하다.

결국 더 빠른 방법을 찾아야한다.

문제의 예제로 준 입력을 바탕으로 규칙을 찾아 보려고 한다.

7
3 1 6 2 7 30 1

먼저 입력받은 추들을 무게 기준으로 오름차순으로 정렬한다.

그리고 추들을 하나씩 저울에 올리기 시작하면 결국 20까지는 모든 무게를 잴 수 있다. 하지만 30을 올리는 순간 50이 되어버리고 21부터 29까지의 무게는 알 수가 없게된다.

이를 통해 임의의 무게 1부터 X의 무게를 잴 수 있다면 다음 올릴 추(arr[i])를 통해 x+1의 무게를 잴 수 있다면 x+arr[i]까지의 무게를 모두 잴 수 있다는 의미이다.

이 생각을 빨리 했지만 제일 작은 추의 무게로 1이 아닌 다른 추가 온다면 1을 출력해야한다는 것을 빼먹어 틀렸다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    static int n, m, k;
    static int max = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);

        int[] arr = new int[n];

        String[] line = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(line[i]);
        }

        Arrays.sort(arr);

        int sum = arr[0];
        int ans = 0;
        if (arr[0] != 1) {
            ans = 1;
        }
        else {
            for (int i = 1; i < n; i++) {
                if (arr[i] > sum + 1) {
                    ans = sum;
                    break;
                }
                sum = sum + arr[i];
            }
            ans = sum + 1;
        }
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}