[Algorithm] 저울

Jong Min ·2025년 4월 10일

algorithm

Algorithm

목록 보기

19/30

⚖️ 백준 2437번 - 저울

🔗 저울

📌 문제 설명

하나의 양팔 저울이 있습니다.
저울의 한 쪽에는 추들만 올릴 수 있고, 다른 한 쪽에는 물건 1개만 올릴 수 있습니다.

이때 주어진 추들을 이용해서 측정할 수 없는 양의 정수 무게 중 가장 작은 값을 구하는 것이 목표입니다.

🎯 입력 조건

첫째 줄: 추의 개수 N (1 ≤ N ≤ 1,000)
둘째 줄: 추의 무게를 나타내는 N개의 양의 정수 (각각 1 이상 1,000,000 이하)

📝 예제

// 입력
7
3 1 6 2 7 30 1

// 출력
21

💡 해결 방법

이 문제는 그리디 알고리즘(Greedy Algorithm)을 사용하는 대표적인 문제입니다.

✅ 핵심 아이디어

추를 오름차순으로 정렬합니다.
sum이라는 변수를 사용하여 지금까지 측정 가능한 무게의 최대값을 저장합니다.
처음엔 sum = 0이고, 측정 가능한 구간은 1 ~ sum입니다.
매번 추의 무게가 sum + 1보다 작거나 같으면, 그 추를 추가하여 측정 가능한 범위를 확장할 수 있습니다.
하지만 sum + 1보다 크다면, sum + 1이 바로 측정할 수 없는 최소 무게가 됩니다.

래서 그 sum + 1이 바로 정답이야.

🧩 예시 설명 (추: 3, 1, 6, 2, 7, 30, 1)

정렬하면 → [1, 1, 2, 3, 6, 7, 30]

하나씩 보며 sum을 늘려보면

단계	추 무게	현재 sum	sum + 1	추 ≤ sum+1	새로운 sum	측정 가능 무게
1	1	0	1	✅	1	1
2	1	1	2	✅	2	1~2
3	2	2	3	✅	4	1~4
4	3	4	5	✅	7	1~7
5	6	7	8	✅	13	1~13
6	7	13	14	✅	20	1~20
7	30	20	21	❌	break!	❌ 21 못 만듦

그래서 정답은 21입니다!

✅ 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
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));

		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

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

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