[BOJ] 2512번 예산 자바

문제

https://acmicpc.net/problem/2512 

2512번: 예산

문제

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

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
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 이하이다. 

출력

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

풀이

#이분탐색

이분탐색을 이용하여 최대 예산을 배정한다. 문제에서 요구하는 N의 범위가 크기 때문에 완전탐색을 이용하면 시간초과가 뜬다. 따라서 이분탐색을 이용한다.

left = 0, right = (요구하는 예산 중 가장 큰 값)으로 시작한다. 요구하는 예산보다 더 큰 상한값은 최대 배분하는 데에 필요하지 않기 때문에 요구하는 예상 중 최대값이 right가 된다.

코드

package BOJ.binarysearch;

import java.io.*;
import java.util.*;
public class No2512_예산 {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int N=Integer.parseInt(br.readLine());
        arr=new int[N];
        StringTokenizer st=new StringTokenizer(br.readLine());
        int sum=0;
        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); //정렬
        int left=0; //상한선으로 가능한 수 중 최소
        int right=arr[arr.length-1]; //예산으로 가능한 수 중 최대(최대로 요구하는 돈을 넘어서는 상한선은 필요 없음)

        int answer=0;


        while(left<=right){ //<로 하면 틀림
            int mid=(left+right)/2;

            int give=0;
            for(int num:arr){
                give+=Math.min(mid, num);
            }

            //예산보다 주는 돈이 더 적거나 같은 경우 -> 더 넉넉하게 잡아도 된다는 뜻
            if(give<=M){
                answer=mid; //answer=Math.max(answer, mid)
                left=mid+1;
            }
            //예산보다 주는 돈이 더 큰 경우 -> 예산 총액 초과, 더 타이트하게 잡아야 한다는 뜻
            else{
                right=mid-1;
            }
        }

        System.out.println(answer);
    }
}