[Algorithm Study] 백준 2512

문제 출처 : https://www.acmicpc.net/problem/2512

문제 접근

위의 문제는 최대 배분해 줄 수 있는 예산액을 구하는 문제로 이분 탐색 알고리즘을 활용하여 문제를 해결했습니다. 요청된 예산액 중 최대 예산액을 기준으로 이분 탐색을 거치며 총 예산액을 넘지 않은 선에서 최대 요청 예산액을 도출했습니다.

소스 코드

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

public class Main {

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        long[] arr = new long[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        long cost = Integer.parseInt(br.readLine());
        long answer = 0;
        Arrays.sort(arr);
        long s = 0;
        long e = arr[N-1];
        while(s <= e){
            long mid = (s+e)/2;
            long sum = 0;
            for(long money : arr){
                if(money > mid) sum += mid;
                else sum += money;
            }
            if(sum > cost){
                e = mid - 1;
            }
            if(sum <= cost){
                s = mid + 1;
                answer = Math.max(answer, mid);
            }
        }
        System.out.println(answer);
    }
}