[백준] 2512 : 예산 - Java

• 백준 문제 URL

---

문제 요약

각 지방이 요청한 예산이 있고,
총 예산 한도 내에서 모든 지방에 동일한 상한액을 배정할 때,
최대 가능한 상한액을 구하는 문제다.

즉,

• 각 지방 arr[i]에 min(요청액, 상한액)을 배정
• 총합 ≤ 총예산이 되는 최대 상한액을 찾는다.

---

핵심 아이디어

"모든 지방에 동일한 상한액을 배정" → 이진 탐색으로 상한액 결정

핵심은 이진 탐색 범위 설정:

• 최소: 0원
• 최대: 가장 큰 지방의 요청액

중간값 mid로 배정했을 때 총액을 계산:

• 총액 > 예산 → 상한액 하향 (end = mid - 1)
• 총액 ≤ 예산 → 상한액 상향 가능 (answer = mid, start = mid + 1)

---

알고리즘 핵심 로직

1. 최대 요청액 찾기 → 이진 탐색 상한
2. start = 0, end = maxRequest
3. while start <= end:
   mid = (start + end) / 2
   
   total = 0
   for 각 지방:
       total += min(mid, 요청액)
   
   if total > 예산:
       end = mid - 1
   else:
       answer = mid
       start = mid + 1

---

전체 코드 (제출용)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine()); // 지방 수

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        int maxByCity = Integer.MIN_VALUE;

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

        Arrays.sort(arr);
        int limit = Integer.parseInt(br.readLine()); // 총 예산

        int startIdx = 0;
        int endIdx = maxByCity;
        int answer = 0;

        while (startIdx <= endIdx) {
            int mid = (startIdx + endIdx) / 2;
            long total = 0; // 오버플로우 방지

            for (int i = 0; i < arr.length; i++) {
                total += Math.min(mid, arr[i]);
            }

            if (total > limit) {
                endIdx = mid - 1;
            } else {
                answer = mid;
                startIdx = mid + 1;
            }
        }

        System.out.println(answer);
    }
}

---

예제 시뮬레이션

입력:

n = 3
요청액 = [120, 110, 140]
총예산 = 485

이진 탐색 과정:

mid=70: total = 70+70+70 = 210 ≤ 485 → answer=70, start=71
mid=127: total = 120+110+127 = 357 ≤ 485 → answer=127, start=128
mid=168: total = 120+110+140 = 370 ≤ 485 → answer=168, start=169
mid=204: total = 120+110+140 = 370 ≤ 485 → answer=204, start=205
...
최종 상한액 = 149원

---

핵심 포인트 정리

• 동일 상한액 배정 → Math.min(mid, 요청액)
• 조건 충족 시 최대값 탐색 → answer = mid, start = mid + 1
• long 타입 필수 (n * 10^9 오버플로우 위험)