[백준] 2512 예산 - JAVA

백준 2512 예산 Silver II - JAVA 📌

https://www.acmicpc.net/problem/2512

문제 설명

문제 풀이

---

접근 💡

이 문제의 핵심은 주어진 총액을 초과하지 않고 상한액을 설정하는 것이다.

지방마다 요청하는 예산이 주어지고 모든 요청을 배정할 수 없으면 상한액을 정해서 초과분을 상한액에 맞춰 배정하야 한다.

상한액을 계속 조정해가면서 총 배정액이 주어진 총액을 넘지 않도록 해야한다.

이 조건 속에서 가능한 최대 상한액을 찾아야 한다.

 

최대 예산이 10억이므로 이분탐색으로 효율적으로 상한액을 찾아보자!

 

1. 탐색 범위를 설정해보자.

    정렬을 한 후에 최소상한액을 0, 최대 상한액을 arr[N - 1]과 주어진 총액의 최댓값으로 설정한다.

2. 상한액을 logN으로 탐색해보기 위해 이분탐색을 통해 mid를 찾는다. (l + r) / 2 = mid는 현재의 상한액이 된다.

3. 각 지방의 요청 금액과 mid를 비교하여 total을 계산해보자!

4. total > max 이면 상한액을 줄여야 하므로 r = mid - 1, total < max 이면 상한액을 늘려야 하므로 l = mid + 1 후 현재 상한액을 갱신한다. total == max일 때 상한액이 정답이 되므로 break를 통해 탐색을 끝내주자.

 

최종적으로 탐색 범위가 좁혀지면 가장 큰 상한액이 구해지게 된다. 시간복잡도는 정렬과 이분탐색을 하므로 O(N logN)이 된다.

코드 💡

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

public class Main {

    static int N, max, ans;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        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);
        max = Integer.parseInt(br.readLine());

        ans = 0;
        bs();
        System.out.println(ans);

    }

    private static void bs() {
        int l = 0;
        int r = Math.min(arr[N - 1], max);

        while (l <= r) {
            int mid = (l + r) / 2;
            int total = 0;
            for (int cost : arr) {
                if (cost > mid) {
                    total += mid;
                    continue;
                }
                total += cost;
            }

            if (total == max) {
                ans = mid;
                break;
            }
            if (total > max) r = mid - 1;
            else if (total < max) {
                ans = Math.max(ans, mid);
                l = mid + 1;
            }
        }
    }
}