[BOJ] 백준 2437번 : 저울 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/2437

2437번: 저울

문제

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

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

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

 

풀이

정렬과 그리디 알고리즘을 활용한 문제였습니다. 제가 생각한 전반적인 로직은 다음과 같습니다.

1. 추는 오름차순으로 정렬되어 있다.

2. 추[0] ~ 추[n-1]의 무게의 합을 m이라고 하면 1~m사이의 무게는 추[0]~추[n-1]을 이용해 만들 수 있다.

 

경우1. 추[n] <= m + 1

=> 추[0] ~추[n]을 이용해 1~(m+추[n])의 무게를 표현 가능하다.

 

경우 2. : 추[n] > m+1

=> 추[0]~추[n]을 이용해 m+1의 무게는 표현이 불가능하다.

 

예를 들어, 추의 무게가 각각 1, 2, 3, 4가 주어져있다고 가정해 봅시다.

처음에 m = 0에서 시작해서 1부터 4까지 차례대로 조건을 비교합니다.

1 <= m + 1에 해당하므로 m = 1이 됩니다.

2 <= m + 1에 해당하므로 m = 3가 됩니다.

3 <= m + 1에 해당하므로 m = 6이 됩니다.

4 <= m + 1에 해당하므로 m = 10가 됩니다.

따라서 주어진 추로 만들 수 있는 최대합은 10이므로 표현할 수 없는 무게의 최솟값은 11, 즉 m + 1이 되는 것입니다.

위의 로직을 코드로 옮기면 아래와 같습니다.

 

소스 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
 
        int[] weight = new int[N]; // 추의 무게
        st = new StringTokenizer(br.readLine());
 
        boolean isOne = false; // 입력된 추의 1이 존재하는가?
        for (int i = 0; i < N; i++) {
            weight[i] = Integer.parseInt(st.nextToken());
 
            if (weight[i] == 1) {
                isOne = true;
            }
        }
 
        if (!isOne) { // 입력된 추의 무게 중 1이 없으면, 표현할 수 없는 가장 최소 무게는 1이다.
            bw.write("1\n");
            bw.close();
            br.close();
            return;
        }
 
        Arrays.sort(weight); // 추의 무게를 오름차순으로 정렬한다.
 
        int sum = 0; // 추의 무게의 부분합
        for (int i = 0; i < N; i++) {
            // 현재 sum은 0부터 i - 1까지 추의 무게의 합이 담겨있다.
            // 이것은 1 ~ sum 사이의 무게는 weight[0] ~ weight[i - 1]를 이용해서
            // 표현가능하다는 의미이다.
            
            // 만약 weight[i] <= sum + 1이라면, 1 ~ sum + 1 사이의 무게를
            // 표현할 수 있게된다는 의미이므로 sum += weight[i]를 해 주면 된다.
            // 그렇지 않을 경우, sum + 1은 표현할 수 없으므로 반복문을 종료한다.
            if (weight[i] <= sum + 1) {
                sum += weight[i];
            } else {
                break;
            }
        }
 
        bw.write((sum + 1) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.