백준 2512번 : 예산 (Java)

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

2512번: 예산

---

[풀이]

• 이분 탐색과 관련한 문제입니다.
• mid 변수는 내야할 세금을 의미하며 sum 변수는 모든 지방의 세금에 대한 합입니다.
• 내야할 세금을 낼 수 있는 경우에는 그 세금에 대한 값을 sum에 더하고 낼 수 없는 곳은 최대의 세금을 sum에 더합니다.
• 이후 sum 변수를 이용해서 내야할 세금보다 많은 경우에는 세금을 줄이는 식으로, 반대의 경우에는 세금을 높여서 최적의 경우를 찾습니다.

---

[코드]

 

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

public class Main {
    static int N;
    static long M, answer;
    static int[] arr;

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

        Arrays.sort(arr);

        long start = 0;
        long end = arr[N - 1];

        while (start <= end) {
            long mid = (start + end) / 2;
            long sum = 0;
            for (int value : arr) {
                if (value >= mid)
                    sum += mid;
                else
                    sum += value;
            }
            if (sum > M)
                end = mid - 1;
            else {
                start = mid + 1;
                answer = Math.max(answer, mid);
            }
        }
        System.out.println(answer);
    }
}