[BOJ] 2512번 - 예산

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

2512번: 예산

 

분류 : 이분 탐색

 

public class Main {

    public static PrintWriter out;

    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));

        int N = sc.nextInt();
        int[] contry = new int[N];
        int Tsum = 0;
        int Tmax = 0;
        for(int index = 0; index<N;index++){
            contry[index] = sc.nextInt();
            Tsum+= contry[index];
            Tmax = Math.max(Tmax, contry[index]);
        }
        long budget = sc.nextLong();
        int s = 1;
        long max =0;
        long e = 1000000001;
        if(Tsum<=budget){
            out.println(Tmax);
        }
        else{
        while(s+1<e){
            long sum =0;
            int mid = (int) ((s+e)/2);
            for(int index=0;index<contry.length;index++)
            {
                if(mid>=contry[index]){
                sum +=contry[index];
                }
                else{
                    sum+=mid;
                }
            }
            if(sum>budget){
                e = mid;
            }
            else{
                s = mid;
            }
        }
        out.println(s);
        }
        out.flush();
    }
}

 

문제 풀이 : 최저 예산 1부터 최고 예산 1,000,000,000을 정해놓고서 이분 탐색을 통해 최대 예산을 추적해간다!

 

중간 지점(Mid)을 정해서 각각의 필요 예산과 비교하여 크면 필요 예산을 더하고 작다면 mid를 더한 후 Sum 값이 주어진 전체 예산과 비교 판단한다.

이때 , sum> budget이라면 최고 예산을 mid로 sum <=budget이라면 최저 예산을 mid로 대입한 후에 이분 탐색을 계속 반복하다 보면 답이 나온다.

 

처음 제출 후 틀렸을때 간과했던 것이 있다면 , 지방에서 각각 요구하는 예산의 합이 전체 예산보다 작다면 그냥 지방의 요청 예산중 최댓값을 답으로 출력하면 된다..