BOJ) 케이크 자르기

케이크 자르기

17179번: 케이크 자르기

풀이

 

문제를 처음 봤을 때, 요즘 DP 문제를 많이 풀어서 그런지 Dp가 가장 먼저 떠올랐다.

하지만, 너무 복잡하고 생각할 것이 많아지면서 DP는 아니라고 생각하고 포기했다.

질문 게시판을 살펴보니까, 이분 탐색이라는 얘기가 많았다.

이분 탐색보다 더 좋은 방법이 있을까 생각해보다가, 그냥 이분탐색으로 풀게 되었다.

 

예전 카카오 문제 중에 돌다리 건너기(?) 문제와 유사하다고 생각한다.

돌다리 문제의 한 번에 건너 뛸 수 있는 거리 k가 케이크의 조각 길이에 대칭된다.

 

이분 탐색에서 mid를 답이 될 조각 케이크그 크기로 설정해준다.

그럼 left와 right는 자연스럽게 0, L (롤 케이크의 총 길이)이 된다.

 

케이크를 조각낼 수 있는 지점을 돌면서, 이전에 자른 지점에서 지금 순회하고 있는 지점까지의 길이가 mid 이상인 곳에서 잘라주면서, 자르는 횟수(Cnt, 문제에서는 Qi로 주어진다)를 하나씩 줄여준다.

 

이분 탐색으로 코드를 짜는 것 자체는 크게 어렵지는 않지만, 이분 탐색으로 풀어야겠다 아니다로 명확하지 않았던 점이 아쉽다.

코테의 9할은 문제 해석인데, 문제에 대해서 하나에 꽂히기 보다는 여러 유형으로 로직을 그려보는 것도 괜찮은 것 같다.

 

코드

 

package remindBOJ;

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        int[] cutArr = new int[M+1];
        cutArr[M] = L;
        for(int i=0; i<M; i++) {
            cutArr[i] = Integer.parseInt(br.readLine());
        }

        int[] cntArr = new int[N];
        for(int i=0; i<N; i++) {
            cntArr[i] = Integer.parseInt(br.readLine());
        }

        solution(M,cutArr,cntArr);
        br.close();
    }

    private static void solution(int m, int[] cutArr, int[] cntArr) {
        for(int cnt : cntArr) {
            System.out.println(getLen(cnt,m,cutArr));
        }
    }

    private static int getLen(int cnt, int m, int[] cutArr) {
        int result =0;
        int left =0, right =cutArr[m];

        while(left <= right) {
            int mid = (left+right)/2;
            if(canCut(mid, cnt, m, cutArr)) {
                left = mid+1;
                result = Math.max(result, mid);
            } else {
                right = mid-1;
            }
        }
        return result;
    }

    private static boolean canCut(int mid, int cnt, int m, int[] cutArr) {
        int prev = 0;
        for (int i = 0; i <= m; i++) {
            if (cutArr[i] - prev >= mid) {
                cnt--;
                prev = cutArr[i];
            }
        }
        return cnt < 0 ? true : false;
    }
}