[JAVA] 백준 2343 기타 레슨_이분탐색

 

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

 

접근 : 

 

 - 블루 레이 크기를 이분 탐색을 통하여 찾는다.

 

 - left = 입력 배열의 max 값, right = 1,000,000,000 으로 지정 후 탐색을 진행한다. 

 

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

 

 

 

코드구현 : 

 

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

public class Main {

    private static boolean calFunc(int[] nums, int mid, int target ){
        int temp_res = 0;
        int count = 1;
        for(int num : nums) {
            if(temp_res + num > mid){
                count++;
                temp_res = num;
                continue;
            }
            temp_res += num;
        }
        return count <= target;
    }

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


        String[] temp = br.readLine().split(" ");
        int n =  Integer.parseInt(temp[0]);
        int m = Integer.parseInt(temp[1]);

        String[] inputs = br.readLine().split(" ");

        int[] nums = new int[n];

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

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

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

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

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