[백준/Java] 2512 - 예산

백준 2512 - 예산

요구사항

• N개 지방의 요청 예산과 총 예산 M이 주어질 때
• 상한액을 정해서 총 예산을 초과하지 않는 최대 상한액을 구하는 문제
• 상한액보다 요청이 적으면 요청액 그대로, 많으면 상한액만 지급

접근 방식

파라메트릭 서치(이분탐색) 로 풀었다.

핵심 아이디어

이분탐색 대상: 상한액 (1 ~ 최대 요청액)
조건: 상한액 mid로 지급했을 때 총합이 M 이하인가?

sum <= M → 가능 → lt = mid + 1, answer 갱신
sum > M  → 불가능 → rt = mid - 1

예외 처리

모든 요청액의 합이 M보다 작으면
→ 상한액 없이 전부 지급 가능
→ 최대 요청액이 정답

코드

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

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().trim());
        int[] moneys = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        int sum = 0;
        for (int i = 0; i < n; i++) {
            moneys[i] = Integer.parseInt(st.nextToken());
            sum += moneys[i];
        }
        int m = Integer.parseInt(br.readLine().trim());

        Arrays.sort(moneys);
        if (sum <= m) {
            System.out.println(moneys[n-1]);
            return;
        }

        int lt = 1, rt = moneys[n-1], answer = 0;
        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            sum = 0;
            for (int x : moneys) sum += Math.min(x, mid);

            if (sum > m) rt = mid - 1;
            else { lt = mid + 1; answer = Math.max(answer, mid); }
        }
        System.out.println(answer);
    }
}

느낀점

• 나무 자르기, 징검다리와 동일한 파라메트릭 서치 패턴이었다.
• "최댓값을 최소화 / 최솟값을 최대화" 키워드가 나오면 이분탐색을 떠올리자.
• 코테에서 비슷한 유형이 나왔는데 실전에서 바로 적용하지 못한 게 아쉬웠다.
• 꾸준히 유형을 익혀두면 다음엔 바로 떠올릴 수 있을 것 같다.