5주차 : 이진탐색 문제2

✔ BOJ_2512

풀이과정

해당 문제를 이분 탐색으로 풀어야하는 이유를 이해하지 못했는데, 아마 시간 문제 때문인 것 같았다.
초반 left인 0은, 상한선이 0 이면 총 예산인 m 안에 모두 지불할 수 있으므로 가능한 최소의 금액이고
초반 right인 money[money.length-1]은 총 예산인 m 안에 모두 지불할 수 없는 가능한 최대의 금액이다.

mid를 구하고, 이를 상한선으로 적용하여 총 필요한 예산을 구하고,
이가 m보다 작다면 left 를 mid+1로 변경하고
이가 m보다 크다면 right를 mid-1로 변경한다.

따라서 해당 left, right를 이분탐색을 이용하여 상한액을 구해야지 시간초과 없이 해당 금액을 구할 수 있음을 확인할 수 있다.

package BaekJoon.Binary;

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

public class BOJ_2512 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 지방의 수
        int n = Integer.parseInt(br.readLine());
        int[] money = new int[n];
        // 지방의 예산 요청
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            money[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(money);
        // 총 예산
        int m = Integer.parseInt(br.readLine());
        int left = 0;
        int right = money[n-1];
        while(left<=right){
            int mid = (left+right)/2;
            int sum = 0;
            for(int o : money){
                if(o >= mid) sum +=mid;
                else sum += o;
            }
            if(sum<=m) {
                //아직 더 낼 수 있으면
                left = mid+1;
            }
            else{
                // 예산 안에서 낼 수 없으면
                right = mid -1;
            }
        }

        System.out.println(right);

    }
}