백준 2437번. 저울 (Java)

Problem

• 문제 링크

 

무게추의 갯수와 무게가 주어졌을 때 주어진 무게추들로 만들 수 없는 가장 최소무게를 구하는 문제입니다.

Solution

문제 예시 3 1 6 2 7 30 1 를 정렬하면 1 1 2 3 6 7 30 이 됩니다.

반복문으로 정렬한 숫자들을 하나씩 더해가면서 누적합을 구합니다.

만약 다음 원소값이 누적합 + 1 보다 크다면 누적합 + 1은 만들지 못하는 무게입니다.

처음에는 누적합까지의 무게는 전부 다 만들 수 있다는 전제가 어떻게 만들어진지 이해가 되지 않았습니다.

그런데 직접 해보면서 손으로도 따라해보니 어렴풋이 이해가 됩니다.

누적합 이라고 생각하지 말고 주어진 무게추들로 만들 수 있는 최댓값 이라고 생각하면 됩니다.

 

예를 들어 위 예시에서 1 1 2 까지의 누적합은 4 입니다.

1, 2, 3, 4 까지는 주어진 추 세개 1 1 2 로 전부 만들 수 있습니다.

그리고 여기에 새로운 무게추 3 이 추가된다면 누적합은 7 이 됩니다.

4 까지는 전부 만들수 있다는 걸 이전에 확인을 했고

새로운 5, 6, 7 은 각각 2+3, 3+3, 4+3 이 되고 2, 3, 4 는 1 1 2 의 추로 전부 구할 수 있었고 새로 추가된 3 무게추까지 있다면 5, 6, 7을 만들 수 있습니다.

시간복잡도는 정렬이 있기 때문에 O(n * logn) 이고 공간복잡도는 O(n) 입니다.

Java Code

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] weight = new int[n];

        for (int i=0; i<n; i++) {
            weight[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(weight);

        int sum = 0;
        for (int i=0; i<n; i++) {
            if (sum + 1 < weight[i]) {
                break;
            }

            sum += weight[i];
        }

        System.out.println(sum + 1);
    }
}