2512. 예산

우선 예산을 오름차순 정렬을 하여 제시된 총액으로 정해진 처음 상한가를 기준으로 연산을 시작한다.

상한액보다 작을 경우 다른 곳에 나누어 줄 수 있는 돈이 더 생기게 되는 것이므로 그 돈을 활용해 다시 상한액을 측정하였다.

모든 경우에서 상한가보다 낮을 경우가 있을 수 있기 때문에 상한가보다 낮을 경우 출력해야할 결과값인 최대 예산을 계속 갱신해주었다.

그 뒤 상한가보다 높은 가격의 예산이 나오게 되면 위에서 정렬을 이미 했기 때문에 그 뒤로부터는 계속해서 상한가보다 높은 예산이 나오게 되므로 예산의 가격이 아닌 한정가와 현재까지 최대값 예산과의 max비교를 통해 결과값을 갱신한 후 더이상의 연산은 모두 한정가와 같으므로 for문을 break 빠져나오게 했다.

 

package november.second;

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

public class B_2512_예산 {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int M = Integer.parseInt(in.readLine());

		Arrays.sort(arr); // 예산 오름차순 정렬

		int limit = M / N; // 처음 가능한 정수 상한액
		int max = 0; // 결과값
		for (int i = 0; i < N; i++) {
			if (limit >= arr[i]) { // 상한액보다 작을 경우
				max = Math.max(max, arr[i]);
				M -= arr[i];
				int k = N - (i + 1);
				if (k > 0) // 다시 상한액을 정한다
					limit = M / k;
			} else { // 이 뒤로부터는 계속 상한가보다 높으므로 최대 예산은 상한가가 된다
				max = Math.max(max, limit);
				break;
			}
		}
		System.out.println(max);
	}
}