[Java] 백준 2512번: 예산

[문제 바로 가기] - 예산

💡 접근 방식

매개변수탐색으로 구현하는 문제!
이분탐색과 비슷한데 매개변수탐색은 정렬된 배열이 아니어도 가능하다.

right는 최대값, mid는 left과 right의 중간 값이다.
mid보다 arr[i]의 값이 클 경우 mid 값을 총 예산 값에 더하고 작을 경우에는 arr[i]을 더한다.
총 예산 값이 주어진 money보다 작을 경우에는 left를 mid + 1, 클 경우에는 right를 mid - 1로 초기화해준다.

익숙해지도록 매개변수탐색 관련 문제를 더 풀어봐야겠다.

풀이

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

/**
 * 백준 2512번 예산
 * - 매개 변수 탐색 사용
 */
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());
		int arr[] = new int[N];
		
		st = new StringTokenizer(br.readLine());
		
		int left = 0;
		int right = -1;
		
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(st.nextToken());
			arr[i] = num;
			right = Math.max(right, arr[i]);
		}
		
		int money = Integer.parseInt(br.readLine());
		
		while (left <= right) {
			int mid = (left + right) / 2;
			long budget = 0;
			
			for (int i = 0; i < N; i++) {
				if (arr[i] > mid) budget += mid;
				else budget += arr[i];
			}
			
			if (budget <= money) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		
		System.out.println(right);
	}
}