[백준 17179] 케이크 자르기(Java)

문제

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

풀이

이분 탐색을 이용해 풀었다.
롤케이크를 잘랐을때 가장 작은 길이의 최댓값을 기준으로 삼았다.

left와 right를 적절히 조절해가면서 mid(롤케이크를 잘랐을때 가장 작은 길이)를 기준으로,
mid를 최소 길이로 하여 잘랐을 때 잘라서 생긴 조각의 개수가 지정된 커트 횟수보다 많으면 left를 늘려주고,
지정된 커트 횟수보다 적으면 right를 줄여주었다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int N;
    public static int M;
    public static int L;
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        M = scan.nextInt();
        L = scan.nextInt();

        int[] input = new int[M+2];
        input[0] = 0;
        for(int i=1;i<=M;i++) input[i] = scan.nextInt();
        input[M+1] = L;

        Arrays.sort(input);
        for(int i=0;i<N;i++){
            int cut = scan.nextInt();
            System.out.println(solution(input, cut));
        }
    }
    public static int solution(int[] input, int cut){
        int left = 0; int right = L;
        int answer = 0;
        while(left<=right){
            int mid = (left+right)/2;
            int prev = input[0];
            int numOfCut = 0;
            for(int i=1;i<=M+1;i++){
                if(input[i]-prev>=mid){
                    numOfCut++;
                    prev = input[i];
                }
            }
            if(numOfCut>cut){
                left = mid+1;
                answer = Math.max(answer, mid);
            }
            else right = mid-1;
        }
        return answer;
    }
}