문제링크

풀이

공유기 설치를 먼저 풀고 나니 쉽게 풀린 문제이다. 전형적인 이분탐색 문제라는 것을 알 수 있다.

1. 지급 예산 총합을 계산하는 메서드 구현
   우선, 특정 상한액 val이 주어졌을 때, 각 지방에 지급할 수 있는 총 예산 금액을 계산하는 메서드를 구현한다.
   • 요청 예산이 상한액 이하라면 요청한 금액 그대로, 요청 예산이 상한액보다 크면 상한액만큼만 지급한다.

    public static int budgetSum(int val) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.min(arr[i], val);
        }
        return sum;
    }

2. 이분 탐색 시작
   상한액의 최댓값을 이분 탐색으로 구하기 위해 탐색 범위를 설정한다.
   상한액의 값을 의미하는 low와 high를 각각 low = 1, high = 요청 예산 중 최댓값 + 1로 지정 후 이분탐색을 시작한다.

int low = 1;
int high = arr[n - 1] + 1;

3. 이분탐색 수행
   이분 탐색을 통해 가능한 상한액 중 예산 총합이 m 이하인 최대 상한액을 찾는다

while (low < high) {
    int mid = (low + high) / 2;

    if (budgetSum(mid) > m) {
        // 예산 총합이 초과 → 상한액이 너무 큼 → 줄여야 함
        high = mid;
    } else {
        // 예산 총합이 여유 있음 → 상한액을 더 키워볼 수 있음
        low = mid + 1;
    }
}

시간복잡도

이분 탐색의 시간 복잡도: $O(log(high-low)) = O(log(100,001-1)) = O(log(100,000))$
예산의 총합을 계산하는 메서드: $O(n) = O(10,000)$

총합계산 메서드는 매 이분탐색마다 수행됨.
총 시간복잡도: $O(log(100,000) * 10,000) = O(약 15 x 10,000)$

코드

package BOJ;

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

public class sol2512 {
    static int n;
    static int[] arr;
    static int m;

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

        n = Integer.parseInt(br.readLine());
        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);

        m = Integer.parseInt(br.readLine());
        int low = 1;
        int high = arr[n - 1] + 1;

        while (low < high) {
            int mid = (low + high) / 2;
            if (budgetSum(mid) > m) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        System.out.println(low - 1);
    }

    public static int budgetSum(int val) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.min(arr[i], val);
        }
        return sum;
    }
}