<이분탐색> 백준 2512 예산

문제

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

2512번: 예산

 

풀이

이분탐색을 사용해서 풀이

출력값인 배정된 예산들 중 최댓값인 정수는 상한가(mid)가 된다.

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

public class Main {
	
	public static void main(String[] args) throws Exception{
		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());
		}
		
		Arrays.sort(arr);
		
		int left=0;
		int right=arr[n-1];
		
		int m = Integer.parseInt(br.readLine());
		int answer=0;
		while(left<=right) {
			int mid = (left+right)/2;
			int total=0;
			for(int i=0; i<n; i++) {
				if(mid<arr[i]) {
					total+=mid;	
				}
				else {
					total += arr[i];
				}
			}
            
			if(total<=m) {
				answer = Math.max(answer, mid);
				left=mid+1;
			}else {
				right=mid-1;
			}
		}
		
		System.out.println(answer);
	}
}