[백준] 예산 2512 - java

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

2512번: 예산

public class 이분탐색 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int arr[] = new int[N];
		int left = 0; int right= 0;
		int sum = 0;
		for(int i=0; i<N; i++) {
			sum += arr[i] = Integer.parseInt(st.nextToken());
			right = Math.max(arr[i], right);
		}
		int M = Integer.parseInt(br.readLine());
		
		if(sum <= M) //배정할 수 있으면
			System.out.println(right);
		else {
			while( left + 1 < right) {
				int mid = (left+right)/2;
				if(isPossible(mid, arr, M)) {
					left = mid;
				}
				else {
					right = mid;
				}
			}
			System.out.println(left);
		}
	}

	private static boolean isPossible(int mid, int[] arr, int m) {
		int sum = 0;
		for(int i=0; i<arr.length; i++) {
			if(mid > arr[i]) {
				sum += arr[i];
			}
			else {
				sum += mid;
			}
		}
		
		if(sum > m) {
			// 배정 불가능
			return false;
		}
		else {
			return true;
		}
	}
}

이분탐색 문제였습니다.

이분탐색은 left엔 가능한 값을 지정, right에는 불가능한 값을 넣는게 핵심이라고 생각합니다.

 

1. 모든 요청이 배정 될 수 있으면 요청한 금액을 그대로 배정

-> 각 지방의 예산을 sum에 모두 더해주고 sum이 총 예산인 M 이하이면 가장 높은 값인 right를 출력합니다.

2. 없다면 최대의 상한값을 배정합니다.

left는 right는 지방의 예산중 가장 높은값(배정이 불가능한 값)을 지정했습니다.

배정이 가능한지는 isPossible()에서 상한액을 기준으로 배정을 해서 그 총액이 M이하이면 true, 아니면 false를 반환했습니다.