[BOJ] 2512번 : 예산

코드

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

public class Main {

    static int n;
    static int[] cities;
    static int budget;
    static int max = -1;

    public static void main(String[] args) {
        input();

        int result = func();

        // result가 1,000,000,001일 경우, 가진 예산으로 모두 나눠줄 수 있으므로
        // 결과는 지방 예산 중 가장 큰 예산이 된다.
        System.out.println(result == 1_000_000_001 ? max : result);
    }

    static void input() {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        cities = new int[n];

        for (int i = 0; i < n; ++i) {
            cities[i] = sc.nextInt();
            max = Math.max(max, cities[i]);
        }

        budget = sc.nextInt();

        sc.close();
    }

    static int func() {
        long left = 1L;
        long right = 1_000_000_001L;
        int result = -1;

        while (right >= left) {
            int mid = (int)((left + right) / 2);

            // 예산 상한이 mid일 때, 써야하는 예산이 주어진 예산 이하일 경우
            // 예산 상한이 더 클 경우에 만족하는 경우가 있는지 탐색해봐야 한다.
            if (budget >= getRequiredBudget(mid)) {
                result = mid;
                left = mid + 1;
            } else {
                // 예산 상한이 mid일 때, 써야하는 예산이 주어진 예산보다 더 클 경우
                // 예산 상한이 더 작은 경우를 탐색해봐야 한다.
                right = mid - 1;
            }
        }

        return result;
    }

    // 예산 상한이 limit일 때, 모든 지방에 예산을 할당할 경우
    // 얼마만큼의 예산을 써야하는지 구하는 함수
    static int getRequiredBudget(int limit) {
        int sum = 0;

        for (int i : cities) {
            // 예산 상한보다 작으면 모든 예산을 할당하고
            // 클 경우 상한 만큼 지급
            sum += Math.min(i, limit);
        }

        return sum;
    }
}