[백준] 2512번 : 예산

2512번: 예산

---

[이분/이진 탐색, Binary Search]

우선, 이진 탐색을 하기 전 입력받은 각 지방의 예산(arr[])을 모두 더한 값과 국가예산의 총액(limit)을 비교하였다.

(총액 >= 예산들의 합) 이라면 예산 중 가장 큰 값을 출력하고 종료한다. 이와 같은 경우가 아니라면 이진 탐색으로 넘어간다.

 

init) left = 1, right = 국가예산의 총액

1) 상한선(mid) 구하기 : mid = (left + right) / n

2) 각 지방의 예산 모두 더하기(sum), 단 예산 > 상한선일 경우 상한선을 더함

3) sum과 limit 비교

 

3-1) sum <= limit

- 상한선의 최대값 갱신

- right = (mid + 1) * n

 

3-2) sum > limit

- left = (mid - 1) * n

# Code </>

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        long arr[] = new long[n], sum = 0;

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

        Arrays.sort(arr);

        long limit = Integer.parseInt(br.readLine());

        if(sum <= limit){
            System.out.println(arr[n-1]);
            System.exit(0);
        }

        long left = 1, right = limit, max = 0;
        while(left <= right){

            long mid = (left + right) / n;
            sum = 0L;

            for(int i=0; i<n; i++)
                sum += Math.min(arr[i], mid);

            if(sum <= limit){

                max = Math.max(max, mid);

                right = (mid + 1) * n;
            }
            else
                left = (mid - 1) * n;
        }
        System.out.println(max);
    }
}