[JAVA] 백준 2512 - 예산

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

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));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        long m = Long.parseLong(br.readLine());

        Arrays.sort(arr);

        long left = 0; // 최소 예산
        long right = arr[n-1]; // 지방 예산 요청중 가장 큰 예산
        long answer = 0;

        while(left<=right){
            long mid = (left+right) / 2; // 상한액
            long sum = 0; // 배정한 금액 총합
            for(int money : arr){
                if(money >= mid) sum += mid; // 상한액이상이면 상한액으로 배정
                else sum += money; // 상한액보다 작으면 예산 요청 금액으로
            }
            if(sum > m){ // 국가예산 총액보다 배정 금액 총합이 크면
                right = mid-1; // 작은 범위의 상한액으로 탐색
            }else{ // 국가예산보다 배정 금액 총합이 작거나 같으면
                left=mid+1; // 큰 범위의 상한액으로 탐색
               // answer = Math.max(answer, mid);
            }
        }
        System.out.println(right); // 배정된 예산의 최대 금액
    }
}