[C++/BOJ] 17179 : 케이크 자르기 (이진탐색)

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

문제

생일을 맞이한 주성이가 생일 파티를 준비하려고 한다. 주성이는 일반 케이크 대신 평소 좋아하던 롤 케이크를 준비했다. 롤 케이크에는 장식이 존재해서 특정 위치에서만 자를 수 있다. 주성이는 롤 케이크 조각을 파티에 올 친구의 수 만큼 준비하고 싶어서, 가장 작은 조각의 크기를 미리 알아보기로 했다. 하지만 짓궂은 주성이의 친구들은 생일파티에 몇 명이 참석하는지 직접적으로 알려주지를 않는다. 그래서 몇 개의 수를 목록에 적어, 각 수만큼 조각을 만들었을 때 가장 작은 조각의 길이의 최댓값을 구하려고 한다.

예를 들어 70cm의 롤 케이크에 자를 수 있는 지점이 5군데(10cm, 20cm, 35cm, 55cm, 60cm)가 있다고 하자. 만약 목록에 적힌 수 중 하나가 3이라면 이때 가장 작은 조각의 길이는 최대 15cm이다. 예를 들어 20cm, 35cm, 55cm 지점을 자를 때 최대가 된다.

입력

첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000)

다음 M줄에 걸쳐 자를 수 있는 지점을 나타내는 정수 Si가 주어진다. (1 ≤ Si < L)

다음 N줄에 걸쳐 자르는 횟수를 나타내는 정수 Qi가 주어진다. (1 ≤ Qi ≤ M)

Si는 오름차순으로 주어지고 중복되는 수는 없으며, Qi도 마찬가지이다.

출력

N개 줄에 걸쳐 각 목록에 있는 횟수대로 롤 케이크를 잘랐을 때 가장 작은 조각의 길이의 최댓값을 출력한다.

---

 

골드 5 이진탐색 문제.

케이크 조각의 길이를 기준으로 left, mid, right을 정한다.

이때 mid 는 구하려는 가장 작은 케이크 조각의 길이이고, 이 mid의 최댓값을 구하면 되는 문제.

 

처음에 n이 조각 수인줄 알고 풀었다가 틀렸음

조각 수가 아니라 자르는 횟수라서 for 문 끝난 후에 cut++를 해줄 필요가 없었다.

 

그리고 만약 자른 횟수가 동일해도, 마지막 조각이 mid보다 커야했기 때문에 아래의 조건문을 추가해주어야 했다.

if(tmp == cut && l-cutted < mid)

 

근데 이분탐색 문제 풀때 계속 헷갈리는 부분이

 

위에 43번째 ~ 48번째 조건문에서 left, right 값 정해줄때

43번째 줄 코드에서

cut < tmp

이렇게 해서 푸는거랑

cut <= tmp

이렇게 푸는게 답이 다르게 나오는데....왜그런지 잘 모르겠다

=을 붙이는 기준이 뭔지.. 어디에 갖다붙여야하는지 아직 헷갈림

 

 

 

 

나의 풀이

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    int m;
    int l;
    vector<int> s;
    int tmp;
    cin >> n >> m >> l;
    for (int i = 0; i < m; ++i) {
        cin >> tmp;
        s.push_back(tmp);
    }

    for (int i = 0; i < n; ++i){
        cin >> tmp;

        int left = 0; // 조각 길이를 알아내는 것이므로 조각 길이 기준 
        int right = l;
        int mid; // 최소 조각길이의 최댓값
        
        while (left <= right){
            mid = (left + right) / 2;
            int cut = 0;
            int cutted = 0;
            for (int i = 0; i < m; ++i){
                if (s[i] - cutted >= mid){
                    cut++;
                    cutted = s[i];
                }
            }
            // cut++; // 조각 수가 아니라 자른횟수임
            
            if(tmp == cut && l-cutted < mid) {// 같을때 마지막 조각이 mid보다 커야하는데 작으면
                right = mid - 1;
            }
            else if (cut < tmp){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        // cout << left << " "<< mid<<" "<< right<< '\n';
        cout << right << "\n";
    }
}