[BOJ] 2512: 예산 (JAVA)

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

 

풀이

 

나무자르기 랑 비슷한 이분탐색/매개변수 탐색 문제

 

이분탐색은 시간복잡도가 O(logN)이다.

배열을 순회할 경우 O(N)이 걸리는데,이에 비하면 굉장히 효율적이라고 볼 수 있다.

 

arr배열을 한바퀴 돌면서, 

상한예산 < 지자체별 신청한 예산 일 경우, 상한 예산을 더해주고

상한예산 > 지자체별 신청한 예산 일 경우, 지자체별 신청한 예산을 더해줬다.

상한예산별 budget이 M보다 작으면,

상한예산을 높여야하기 때문에 left값을 mid+1로 바꿔준다.

(mid 보다 작은 값들은 볼 필요가 없기 때문.)

 

상한예산별 budget이 M보다 크면,

상한예산을 줄여야하기 때문에 right값을 mid-1로 바꿔준다.

(mid 보다 큰 값들은 볼 필요가 없기 때문.)

 

전체코드

package CodingTest;

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

public class 실버2_2512_예산 {
	static int N, M, left, right;
	static int[] arr;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		
		arr = new int[N];
		left = 0; right = -1;
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			right = Math.max(right, arr[i]);
		}
		
		M = Integer.parseInt(br.readLine());
		
		Check();
		
		sb.append(right);
		bw.write(sb.toString());
		bw.close();
	}
	public static void Check() {
		while(left <= right) {
			//상한 예산
			int mid = (left + right)/2;
			long budget = 0;
			
			for(int i=0; i<N; i++) {
				if(arr[i] < mid) {
					budget += arr[i];
				}else {
					budget += mid;
				}
			}
			
			if(budget <= M) {
				left = mid + 1;
			}else {
				right = mid - 1;
			}
		}
	}
}