[Java] 백준 2512 예산

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

난이도

실버2

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.
예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.

내 코드

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

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[] num = new int[N];
		int tmp = 0, max = -1;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			num[i] = Integer.parseInt(st.nextToken());
			tmp += num[i];
			max = Math.max(max, num[i]);
		}
		int total = Integer.parseInt(br.readLine());

		if (tmp <= total) {
			System.out.println(max);
		} else {
			int left = 1, right = max, mid = 0;
			while (left <= right) {
				mid = (left + right) / 2;
				int sum = 0;
				for (int i = 0; i < N; i++) {
					sum += Math.min(num[i], mid);
				}
				if (sum > total) {
					right = mid - 1;
				} else {
					left = mid + 1;
				}
			}
			System.out.println(right);
		}
	}
}

입력을 받으면서 가장 큰 값을 right으로 설정하기 위해 max값을 따로 저장했다.
left는 1로 설정하고 둘의 중간값인 mid를 상한선으로 가정하고 이분탐색을 실행했다.

반복문을 돌면서 mid 혹은 mid보다 작은 배열의 값은 원래 값을 더해서
그 값이 전체 합산 값보다 크다면 right를 mid-1로 설정하고
그 외라면 left를 mid+1로 설정했다.

이분탐색 문제는 이론은 아는데 코드로 풀면 자꾸 실수한다..
까먹지 않게 주기적으로 다시 풀어줘야 하는 유형인 것 같다.