[자바] 백준 2512번: 예산

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

2512번: 예산

 

예전에 풀었던 나무자르기와 동일한 문제였다.

그 땐 분명히 풀었는데,

똑같은 로직으로 똑같이 풀려고 했는데도

코드를 짜기 힘들었다.

 

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

public class P2512 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		Integer[] arr = new Integer[n];
		long sum = 0;

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			sum += arr[i];
		}

		int m = Integer.parseInt(br.readLine());

		Arrays.sort(arr, Collections.reverseOrder()); // 내림차순 정렬

		if (sum <= m) {
			System.out.println(arr[0]);
			return;
		}

		int limit = 0;
		long over = sum - m;
		long cut_sum = 0;
		for (int i = 0; i < n; i++) {
			int cut = arr[i] - limit;

			if (cut == 0)
				break;
			cut_sum += cut;
			if (cut_sum > over) {
				limit += (cut_sum - over) / (i + 1);
				cut_sum -= ((cut_sum - over) / (i + 1)) * (i + 1);
			}

		}

		System.out.println((limit < 0) ? 0 : limit);
	}

}

과도하게 예산 컷을 한 경우에

리미트를 다시 올려줘야하는데

리미트는 정수로만 올라가기때문에 딱 맞아 떨어지지 않아서 

cut_sum을 정확하게 리미트를 올린 만큼 계산해서 더해줘야 뒤탈이 없다.

(cut_sum-=((cut_sum-over)/(i+1))*(i+1))