[백준/Java] 2512 예산

문제 분석

문제를 보면, 입력의 값이 엄청나게 큰 것을 확인할 수 있다. BruteForce를 사용하는 것은 불가능해 보이며, '정해진 총액 이하에서 가능한 한 최대의 총 예산'와 같은 말에서 이분 탐색의 향기가 솔솔난다.

상한액을 mid로 설정하여, 총예산 보다 큰 경우는 max 값을 mid - 1로 설정하여 상한액을 낮춘다. 총예산 보다 같거나 작은 경우는 min 값을 mid + 1로 설정하여 상한액을 높인다. 우리가 구해야 할 값은 max 값이므로 while 문이 끝나는 경우(min > max), max 값이 아닌 min 값이 움직이게 만든다.

남은 알고리즘은 일반적인 이분 탐색과 동일하게 구현하면 된다.

 

문제 풀이

import java.util.Scanner;

public class Main {

    static int N, M, min, max, mid;
    static int[] budget;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        budget = new int[N + 1];
        max = Integer.MIN_VALUE;
        min = 0;
        for (int i = 1; i <= N; i++) {
            budget[i] = sc.nextInt();
            max = Math.max(max, budget[i]);
        }
        M = sc.nextInt();

        findMaxLine();

        System.out.println(max);
    }

    public static void findMaxLine() {
        while (min <= max) {
            mid = (min + max) / 2;

            int allBudget = 0;
            for (int i = 1; i <= N; i++) {
                allBudget += (budget[i] >= mid) ? mid : budget[i];
            }

            if (allBudget > M) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
    }
}