[백준 17179번] 케이크 자르기 JAVA

[백준 17179번] 케이크 자르기 JAVA

케이크 자르기

이분탐색은 가장 감을 잡기 어려웠던 문제였다. 이분탐색이라는 것 자체는 알고 있었는데 이걸 활용하려고 하니 도대체 무엇을 탐색해야할지 모르겠다.

문제를 읽어보면 가장 작은 조각의 길이의 최대값을 출력하라라고 되어있다.

이분탐색에서는 우리가 찾고자하는 값을 정렬하여 이분탐색한다. 근데 문제에서 찾고싶은 값은 가장 작은 조각의 길이의 최대값? 가장 작으면서 최대값이라니 도저히 같이 쓰일수 없는 단어 두개가 같이 쓰였다.(작으며 최댁삾...)

이제부터 잘 생각해보자.

1. 케익을 Q등분 할 것이다.
2. Q등분 했을때 그중에는 가장 작은 길이를 가진 조각이 나온다
3. Q등분할 수 있는 방법은 엄청 많다.

이렇게 생각하면 갑자기 브루트포스 방식으로 풀어야 한다. 이렇게 생각하면 안된다. 이분탐색의 특징을 살려서 생각해 보자.

1. 어찌됬든간에 우리가 찾으려는 정답은 케익조각의 길이이다.
2. 케익 조각은 1조각또는 2조각 또는 n조각이 나올 수 있으니까 조각의 범위는 0~케익의 최대길이 이다.
3. 임의로 가장 작은 조각의 길이를 정해보자(이게 mid 값이다.)
4. N등분을 할때 mid보다 작게 자를 수 없다. 결국 mid보다 크게 잘랐을때 자르는 횟수가 N보다 작아지거나 N보다 커지는 경우가 생긴다.
5. N보다 적게 잘라야한다면 그말인 즉슨 우리가 정한 mid의 크기가 너무 커서 자주 자를수 없다는 뜻
6. 똑같은 생각으로 N보다 많이 잘라야한다면 그말인 즉슨 우리가 정한 mid의 크기가 너무 작아서 자주 자를수 있다는 뜻.
7. 위의 생각이 도출된다면 이제 mid의 범위를 이분탐색으로 찾아가면 된다.

내가 썼지만 나도 정확히 설명하기가 힘들다. 근데 정말 이 글을 잘 읽고 코딩을 다시 보면 이해가 될 것이다. 이분탐색 문제들의 포인트는 우리가 찾고자 하는 값을 올바르게 인식하고 그 값을 정하는 기준을 알아야 하는 것 이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

import static java.util.stream.Collectors.toList;

public class Main {
    public static void main(String [] args) throws IOException {
       Scanner scan = new Scanner(System.in);
       int n = scan.nextInt();
       int m = scan.nextInt();
       int l = scan.nextInt();
       int[] cakes = new int[m+1];//마지막 케익 길이까지 받기위해서 +1
       for(int i=0;i<m;i++){
           cakes[i] = scan.nextInt();
       }
       cakes[m] = l;
       //n번 자르는 횟수 확인

       for(int i = 0 ; i<n;i++){
           int answer = 0;
           int q = scan.nextInt();  //자르는 횟수
           int low = 0;
           int high = l;
           while(low<=high) {
               int mid = (low+high)/2;
               if (checkCake(low, high, mid, cakes, q)) {
                   low = mid + 1;
                   answer = Math.max(mid, answer);
               } else {
                   high = mid - 1;
               }
           }
           System.out.println(answer);
       }

    }

    public static boolean checkCake(int low, int high, int mid, int[] cakes,int q){
        int prev=0;
        for(int i=0;i<cakes.length;i++){
            if(cakes[i]-prev >= mid){
                q--;
                prev = cakes[i];
            }
        }
        return q <0 ? true : false;
    }
}