[알고리즘] 백준 2512 예산 - JAVA

www.acmicpc.net/problem/2512

2512번: 예산

 

이분 탐색의 기초적인? 문제인것 같다.

 

이분 탐색 알고리즘의 개념이 제대로 잡혀있지 않았던 상태여서 풀이를 하는데 오래걸렸다.

 

각 부서별로 예산이 주어지고, 예산이 부족한 경우에 상한선을 정해서 상한선을 초과하는 예산을 요구하는 부서는 상한선 까지만 예산을 부여한다.

 

이 상한선을 찾기 위해 그냥 완탐을 돌려버리면 시간초과가 뜨기 때문에 이분 탐색이 필요하다.

 

start를 0, end를 최대 예산으로 설정하고 mid값을 상한선이라고 생각한 후

 

현재 시점 상한선이 예산을 초과한다면 end를 mid - 1로, 예산보다 부족하다면 start를 mid + 1로 만들어 가장 최대예산과 근접하게 되는 상한선을 구한다.

 

start가 end보다 커지게 되면 반복문을 종료한다.

 

코드를 보고 이해가 가지 않는다면 이분 탐색에 대해 다시 공부해보자.

 

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;
    static int[] budget;
    static int maxBudget;
    static int sum = 0;

    public static void main(String[] args) throws IOException {

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        n = Integer.parseInt(s);
        budget = new int[n];

        s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");

        for (int i = 0; i < n; i++) {
            budget[i] = Integer.parseInt(st.nextToken());
            sum += budget[i];
        }

        s = br.readLine();
        maxBudget = Integer.parseInt(s);
        // input end

        // 최대값 뽑아내기 쉽도록 정렬
        Arrays.sort(budget);

        System.out.println(binarySearch());
    }

    static int binarySearch() {

        // 예산을 그냥 줄 수 있으면 바로 반환
        if (sum <= maxBudget) {
            return budget[n - 1];
        }

        int start = 0;
        int end = maxBudget;

        while (start <= end) {
            int current = 0;
            int mid = (start + end) / 2; // 상한가

            for (int i = 0; i < n; i++) {
                if (budget[i] > mid)
                    current += mid;
                else
                    current += budget[i];
            }

            // 현재 상한가로 예산을 맞추지 못할 경우에
            if (current > maxBudget) {
                end = mid - 1;
            }
            // 현재 상한가로 예산을 맞추기 부족함
            else if (current < maxBudget){
                start = mid + 1;
            }
            else
                return mid;
        }
        return end;
    }
}