[JAVA] 백준 2512 예산_이분탐색

 

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

 

접근 : 

 

 - left 를 0, right 를 입력 받은 예산의 최대값으로 지정한다.

 

 - 이분 탐색을 진행하면서 예산이 최대치를 이하이면 left 를 증가시키고 초과하면 right를 감소 시킨다.

 

 - 탐색이 완료되는 곳을 정답으로 출력한다.

 

 

 

코드구현 : 

 

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

public class Main {

    private static boolean calFunc(int[] nums, int mid, int target ){
        int temp_res = 0;
        for(int num : nums) temp_res += (num < mid) ? num : mid;

        return temp_res <= target;
    }

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

        int n = Integer.parseInt(br.readLine());
        String[] temp = br.readLine().split(" ");
        int[] nums = new int[n];

        for(int i = 0; i < n ; i++) nums[i] = Integer.parseInt(temp[i]);      

        int m = Integer.parseInt(br.readLine());

        int left = 0;
        int right = Arrays.stream(nums).max().getAsInt();
        int mid = 0;
        int answer = 0;

        while (left <= right) {
            mid = (left + right) / 2;

            if(calFunc(nums, mid, m)){
                answer = mid;
                left = mid + 1;
                continue;
            }
            right = mid - 1;
        }

        System.out.println(answer);
        br.close();
    }
}