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

정환우·2021년 8월 9일
0

백준

목록 보기
15/15

실버 1의 이진 탐색을 이용하는 평범한 문제. 이런 문제는 이진 탐색을 어떻게 활용할지 빨리 생각해 내는 것이 가장 중요한 문제이다.
생각이 빨리 안나서 다른 사람의 풀이를 조금씩 보았기 때문에 복습과 복기 차원에서 문제 설명을 해보려고 한다!

해결 방법 생각하기

첫 번째 시도

처음에 해결하려고 했던 방법은 다음과 같다.
입력 처럼 자르는 지점을 저장해 두는 것이아니라, 자르는 지점을 줬으니까 각 조각의 길이가 생성이 되니까, 그 수열을 저장해 두고 이진탐색을 하는 것이다.

그러니까 예를 들면, 문제에서 예제 입력을

이렇게 주었는데, 70cm짜리 케이크를 10cm, 20cm, 35cm, 55cm, 60cm 지점에서 잘랐으니까 결국 케이크 각 조각은 [10,10,15,20,5,10] 이렇게 나뉘는 것이다. 이 조각들을 놔두거나 합쳐서 3개의 조각으로 만들면 되지 않나? 라는 식으로 접근을 해보기로 했다.

근데 이진 탐색이 익숙하지 않은 탓인지 left, right, mid 값을 잡지 못해서 실패. 다 풀고 나서 지금 보니까 저렇게 풀 수 있을 것 같다는 생각이 든다. 왜냐하면 이 다음에 푼 이진 탐색 문제는 오름차순 입력이 아니라 저렇게 풀었기 때문이다.

하지만, 입력을 조각별로 바꿔주는 절차를 걸쳐야 하기 때문에 귀찮을 수 있다.

정석적으로 풀면 이진 탐색 과정에서 조각의 길이를 구하고, 이렇게 먼저 전처리를 하고 이진 탐색을 해도 되는 문제. 전처리를 하냐 후처리를 하냐 본인 취향 차이인 것 같다.

두 번째 시도

결국 저 지점 배열에 처음과 끝 지점까지 넣어줘서 이진탐색을 시도하기로 했다. 그니까 [0, 10, 20, 35, 55, 60, 70] 이러한 배열에서 이진탐색을 시도하는 것. 그래서 left = 0, right = 70으로 잡고 이진탐색을 돌리면서 조각의 개수를 기준으로 탐색을 돌리는 것이다.

근데 이진탐색은 코드 하나하나가 굉장히 헷갈리고 중요하다. 내가 맞은 코드와 틀린 코드 둘 다 올려서 비교해보려고 한다.

코드

틀린 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n,m,l;
int S[4000000];
int Q[1000];
int main(){
    cin >> n >> m >> l;
    for (int i = 0 ; i<m; i++)
        cin >> S[i];

    for(int i = 0; i<n; i++)
        cin >> Q[i];

    for(int i = 0; i<n; i++){   // Q[i]를 다 따져야한다.
        int thistime = Q[i];    // 이번에 따질 횟수.
        int answer = 0; // 그때 그때 답 구하기.
        int left = 0;
        int right = l;

        while (left <= right) { // 이분 탐색 시작.

            int thiscut = 0;    // 이분 탐색에서 컷팅 횟수 체크.
            int mid = (left + right) / 2;
            int prev = 0;
            for (int j = 0; j < m; j++) { // 이거는 S[i]를 도는 반복문. 이분 탐색을 하려면 이게 꼭 필요하다.

                if(S[j] - prev >= mid)  // 만약 이 조각이 mid 이상이면.
                {
                    prev = S[j];    // 이 조각에서 컷팅을 할 것이기 때문에.
                    thiscut++;
                }
            }

            if(thiscut < thistime)  // 만약 내가 원하는 커팅 수보다 커팅 횟수가 적으면, mid값이 너무 큰 것이다.
            {
                right = mid - 1;
            } else
            {
                left = mid + 1;
                answer = max(answer,mid);
            }
        }

        cout << answer << endl;
    }

    return 0;
}

맞은 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n,m,l;
int S[4000001];
int Q[1000];
int main(){
    cin >> n >> m >> l;
    S[0] = 0;
    S[m+1] = l;
    for (int i = 1; i<=m; i++)
        cin >> S[i];

    for(int i = 0; i<n; i++)
        cin >> Q[i];

    for(int i = 0; i<n; i++){   // Q[i]를 다 따져야한다.
        int thistime = Q[i];    // 이번에 따질 횟수.
        int answer = 0; // 그때 그때 답 구하기.
        int left = 0;
        int right = l;

        while (left <= right) { // 이분 탐색 시작.

            int thiscut = 0;    // 이분 탐색에서 컷팅 횟수 체크.
            int mid = (left + right) / 2;
            int prev = S[0];
            for (int j = 1; j <=m+1; j++) { // 이거는 S[i]를 도는 반복문. 이분 탐색을 하려면 이게 꼭 필요하다.

                if(S[j] - prev >= mid)  // 만약 이 조각이 mid 이상이면.
                {
                    prev = S[j];    // 이 조각에서 컷팅을 할 것이기 때문에.
                    thiscut++;
                }
            }

            if(thiscut <= thistime)  // 만약 내가 원하는 커팅 수보다 커팅 횟수가 적으면, mid값이 너무 큰 것이다.
            {
                right = mid - 1;
            } else
            {
                left = mid + 1;
                answer = max(answer,mid);
            }
        }

        cout << answer << endl;
    }

    return 0;
}

딱 두가지 부분에서 차이가 있는데, 먼저 첫번째 코드는 시작지점과 끝 지점 추가를 해주지 않았고, 가장 중요한 차이는 마지막 if문에서 등호가 포함되어 있는지 아닌지의 차이가 정답을 결정한다.

내 경험상 등호를 넣어야 하는 경우가 있고, 안 넣어야 하는 경우가 있는 것 같은데 이 경우는 넣어야 한다. 왜냐하면 이 문제에서 if문이 의미하는 것은 내가 원하는 커팅 횟수보다 커팅 된 횟수가 적을 때의 경우 인데, 이럴 경우 right 값을 줄여주는 문장이다.

나는 정답을 원하는 커팅수보다 커팅 횟수가 많을 때 정답을 추출해 내는데, 우리는 처음에 시작 지점과 끝 지점을 배열에 넣었으므로, 끝 지점에서 한번 더 커팅을 할 수 있어야 한다. 고로 커팅 횟수가 더 많아야 정답이 되는 것.

이 조건문에 항상 유의하면서 풀어야 한다. 이진 탐색은 그래서 어려운 것 같다. 보통의 데이터들로는 이 조건문이 영향을 끼치지 않지만, 데이터의 크기가 커질수록, 복잡해질 수록 조건문에 굉장히 예민하게 반응할 것이기 때문이다.

이거 때문에 이 문제를 몇번을 틀린건지..

profile
Hongik CE

0개의 댓글