[백준 2512번] 예산

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

package greedy;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Greedy2512 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int left=0;
        int right=-1;
        int []num=new int[N];
        StringTokenizer st=new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            num[i]=Integer.parseInt(st.nextToken());
            right=Math.max(right,num[i]);
        }
        int m=Integer.parseInt(br.readLine());
        while(left<=right){
            int mid=(left+right)/2;
            long budget=0;

            for(int i=0; i<num.length; i++){
                if(num[i]>mid){
                    budget+=mid;
                }else{
                    budget+=num[i];
                }
            }

            if(budget <=m){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }

        System.out.println(right);

    }
}

 

이번 문제는 이분 탐색으로 가운데 값을 찾아나가면서 상한액을 반환하는 문제이다.

필자는 처음에 무식하게 풀었으나 갈수록 경우의 수가 너무 많았다. 따라서 구글링을 하면서 겨우 해결한 문제이다..

 

해당 문제를 풀기 위해서는 left를 0, right를 입력된 값 중 가장 큰 값을 주고, while 문을 통해 left가 right 보다 작거나 같을때를 계속 반복하는 동시에 budget에 예산을 계속 추가해준다. 

이때 budget이 총예산보다 작으면 left에 중간 값 +1을 해주고 만약 크면 right에 중간값 -1을  해주면서 범위를 좁혀나가 상한액을 찾으면 된다. 

 

조금만 방향을 바꿔서 생각하면 문제였다... 나는 아직 창의력이 좀 부족하다.