[JAVA] 백준 2437 저울

U_Uracil·2023년 2월 1일

알고리즘 JAVA

목록 보기

12/19

[백준 2437] https://www.acmicpc.net/problem/2437

문제 조건

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.

문제 입력

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

문제 풀기 전 설계

작은 추는 합쳐서 무겁게 만들 수 있지만, 큰 추는 쪼개서 가볍게 할 수 없으므로 추의 무게를 기준으로 오름차순 정렬해서 처음으로 만들 수 없는 무게가 나올 때까지 탐색하면 된다.

문제 코드

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_2437 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] num = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) num[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(num);
        int sum = 0;

        /*
        직접 몇 번 해보면 규칙이 보인다.
        0부터 시작해 sum + 1 < num[i]일 때 sum + 1이 측정할 수 없는 최소 무게가 된다.
         */
        for (int i = 0; i < n; i++) {
            if (sum + 1 < num[i]) break;
            sum += num[i];
        }

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

}

문제 풀이

max = 만들 수 있는 최대 무게라고 하면

추의 개수가 1개 (이전 max = 0)

추의 무게 = 1, max = 1
추의 무게 > 1, max = 0

-> 1번째 추의 무게로 가능한 경우 = 1

추의 개수가 2개

항상 1번째 추의 무게는 1임 (이전 max = 1)
- 2번째 추의 무게 = 1, max = 2
- 2번째 추의 무게 = 2, max = 3
- 2번째 추의 무게 > 2, max = 1
-> 2번째 추의 무게로 가능한 경우 = 1, 2

추의 개수가 3개

앞의 추가 1, 1일 때 (이전 max = 2)
- 3번째 추의 무게 = 1, max = 3
- 3번째 추의 무게 = 2, max = 4
- 3번째 추의 무게 = 3, max = 5
- 3번째 추의 무게 > 3, max = 2
-> 3번째 추의 무게로 가능한 경우 = 1, 2, 3
앞의 추가 1, 2일 때 (이전 max = 3)
- 3번째 추의 무게 = 1, max = 4
- 3번째 추의 무게 = 2, max = 5
- 3번째 추의 무게 = 3, max = 6
- 3번째 추의 무게 = 4, max = 7
- 3번째 추의 무게 > 4, max = 3
-> 3번째 추의 무게로 가능한 경우 = 1, 2, 3, 4