[백준/C++] 알고리즘 17179번 케이크 자르기

오늘은 백준 알고리즘 17179번 케이크 자르기 문제를 풀어보도록 하겠습니다.

문제부터 보겠습니다.

문제를 보시면 가장 작은 조각의 길이의 최댓값을 구하는 문제입니다. 탐색문제죠.

처음에 일반적으로 완전탐색을 고려합니다. 근데 범위를보니까 L이 400만이고 N이 1000입니다.

완전탐색으로 고려했을때 최소 40억의 연산이 필요하기 때문에 불가능하다는 사실을 알 수 있습니다.

연산의 수가 너무 크기때문에 이분탐색을 생각해보아야 합니다.

그래도 좀 까다로웠던 문제가 아닌가 싶습니다.

​

일단 저는 left = 0, right = l 로 잡고 mid = (left+right )/2로 했습니다. 여기서 mid는 가장작은 조각의 길이의 최대값이라고 가정하였습니다.

그리고 왼쪽부터 오른쪽으로 케이크를 자르도록 하였습니다. 처음에는 mid보다 크면 바로 잘랐고 자른 위치를 prev에 저장하여 이후 자를 때 기준이 0이 아니라 이전에 자른 위치가 되도록 코드를 작성하였습니다.

​

코드는 다음과 같아요.

#include <iostream>
using namespace std;
int n,m,l;
int point[1000];
int target[1000];

void binarySearch(){
    for (int j = 0; j<n; j++) {
        int left = 0;
        int right = l;

    while (left<=right) {
        int mid = (left + right)/ 2;
        int prev = 0 ; int cut = 0 ;
        
        for (int i = 0; i< m; i++) {
            if(point[i] - prev >= mid){
                prev = point[i];
                cut++;
            }
        }

 //조각의 개수가 같고 마지막의 조각의 길이 또한 mid보다 커야하는데 작으면 right= mid -1 조건문으로 보냄
        if( target[j] == cut && l - prev < mid){
         cut = target[j]-1;
        }
        if (cut < target[j] ) {
            right = mid - 1;
        }
        else{
            left = mid + 1 ;
        }
    }
        cout<<right<<"\n" ;
    }
}

int main(){
    cin >> n >> m>>l;   
    for(int i = 0; i < m; i++) cin >> point[i];
    for(int i = 0; i < n; i++) cin >> target[i];
    
  binarySearch();
}