백준 이분탐색 2512

 

한마디로 처음에 left,right를 설정해 놓고 내가 원하는 최적의 값을 맞추어 가는 과정이다.

찾으려는 값이 mid 작으면 right를 mid 보다 한칸 내려주는게 맞다. 

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException{
       BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        StringTokenizer st=new StringTokenizer(br.readLine()," ");
        int []arr=new int[n];
        int left=0;
        int right=-1;
        for(int i=0;i<n;i++){
            arr[i]=Integer.parseInt(st.nextToken());
            right=Math.max(arr[i],right);
        }
        int max=Integer.parseInt(br.readLine());
    while(left<=right){
        long budget=0;
        int mid=(left+right)/2;
        for(int i=0;i<n;i++){
            budget+=Math.min(arr[i],mid);
        }
        if(budget<=max){
            left=mid+1;
        }
        else {
            right=mid-1;
        }
    }
    System.out.println(right);
        
    }
}

 

최소한 작은 값을 더해서 budget에 더해줘가지고 max 값보다 작거나 같으면 left를 mid+1 로 해서 맞추어 주고 

max 값보다 크면 right를 mid-1로 맞추어 준다.