[백준] 2512번 : 예산 – JAVA [자바]

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

2512번: 예산

 

---

• 문제

 

 

---

• 문제 풀이

 

백준 2512번 예산은 실버 2 난이도의 이분 탐색 및 매개변수 탐색 문제이다.

 

이 문제에서는 N개의 예산 요청과 총 예산이 주어진다. 이때, 다음과 같은 조건을 만족하도록 예산을 배정하면 된다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다

 

이 문제는 백준 1654번과 상당히 유사하므로 이 문제를 푸는 것과 풀이를 참고하는 걸 추천한다.

 

이 문제는 이분 탐색을 이용해서 풀 수 있다. 만약 이분 탐색에 대해 더 알고 싶으면 밑에 있는 링크를 참고하면 되겠다.

 

[알고리즘] 이분 탐색 (Binary Search)

 

우선 각 지방의 예산들을 입력받을 때 가장 큰 예산 요청값을 int형 변수인 high에 저장하고 각 요청값들의 합을 int형 변수 sum에 저장한다. 그리고, 이 요청값들의 합인 sum이 총 예산보다 작거나 같으면 그대로 배정을 해도 되므로 가장 큰 예산 값인 high를 출력한다.

 

예산의 상한선을 h로 배정했을 때 각 지방의 배정 예산 합을 계산하는 함수 f를 다음과 같이 정의할 수 있다. 이 함수는 간단하게 상한액과 지방의 예산 중 작은 값을 더한 총 값을 구하는 함수이다.

 

// 상한액을 기준으로 각 지방의 배정 예산 합을 계산하는 함수
static int f(int h) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += Math.min(arr[i], h); // 상한액과 지방의 예산 중 작은 값을 더함
    }
    return total;
}

 

이제 이 상한액인 h를 구하면 되는데 이 h는 이분 탐색을 이용해서 구할 수 있다. 

 

우선 h의 탐색 범위를 살펴보겠다. 예산 배정은 1부터 할 수 있고 최댓값은 이전에 구해놓은 high가 된다. 이 1을 low라고 부르도록 하겠다.

 

이제 예산 상한액의 탐색 범위는 low부터 high가 된다. 이 탐색 범위에서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 배정하면 된다. 이 h값은 다음과 같이 찾을 수 있다.

 

// 이분 탐색 실행
while (low < high - 1) {
    int mid = (low + high) / 2;

    // 상한액(mid)을 기준으로 각 지방의 배정 예산 합을 계산
    if (f(mid) > max) {
        high = mid; // 상한액을 낮게 설정하여 다시 탐색
    } else {
        low = mid; // 상한액을 높게 설정하여 다시 탐색
    }
}

 

우선 low가 high - 1보다 작을 때 계속 loop을 돌려준다. 그리고 이분 탐색은 중간값을 비교해서 탐색 범위를 줄이는 알고리즘이다. 따라서, low와 high의 중간값 mid를 구해주고 f(mid)를 해준다. 전에서 설명했듯이 이 함수 f는 예산 배정액을 h로 했을 때 쓰는 총 예산이다.

 

따라서, f(mid)가 총액인 max보다 크면 이 mid보다 큰 값을 탐색할 필요가 없으므로 탐색 범위를 low에서 mid로 바꿔준다.  반대로, f(mid)가 N보다 작거나 같으면 탐색 범위를 mid에서 high로 바꿔주고 탐색을 계속한다.

 

그리고 이 탐색이 끝났을 때 low가 정해진 총액 이하에서 가능한 한 최대의 총 예산이 된다.

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

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

public class Main {
    static int n;
    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());
        int sum = 0;
        int high = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sum += arr[i]; // 모든 예산 요청의 합 계산
            high = Math.max(high, arr[i]); // 가장 큰 예산 요청 값 저장
        }

        // 총 예산 입력
        int max = Integer.parseInt(br.readLine());

        // 모든 예산 요청의 합이 총 예산 이하인 경우 가장 큰 예산 요청 값을 출력하고 종료
        if (sum <= max) {
            System.out.println(high);
            return;
        }

        // 이분 탐색을 위한 시작점과 끝점 초기화
        int low = 1;

        // 이분 탐색 실행
        while (low < high - 1) {
            int mid = (low + high) / 2;
            
            // 상한액(mid)을 기준으로 각 지방의 배정 예산 합을 계산
            if (f(mid) > max) {
                high = mid; // 상한액을 낮게 설정하여 다시 탐색
            } else {
                low = mid; // 상한액을 높게 설정하여 다시 탐색
            }
        }

        // 결과 출력
        System.out.println(low);
    }

    // 상한액을 기준으로 각 지방의 배정 예산 합을 계산하는 함수
    static int f(int h) {
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += Math.min(arr[i], h); // 상한액과 지방의 예산 중 작은 값을 더함
        }
        return total;
    }
}