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

 

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

 

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

17179번: 케이크 자르기

---

 

 

해결전략

 

이분탐색, 매개변수 탐색

 

---

 

 

 

 

 

 

---

 

 

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
// n: 자르는 횟수, m: 자를 수 있는 위치 개수, l: 롤 케이크의 길이를 저장
int n, m, l;
// v: 자르는 위치를 저장할 벡터
vector<int> v;
 
// 목표한 크기의 조각으로 롤 케이크를 자를 수 있는지 판별
bool isValid(int givenCnt, int piecelength)
{
    int cnt = 0; // 롤 케이크를 자른 횟수
    int cuttingLocation = 0; // 자른 롤 케이크의 위치
 
    // 자를 수 있는 위치를 순회하면서, 목표 횟수에 도달할 때까지 자른다
    for(int i = 0; i < m && cnt < givenCnt; i++)
    {
        if (v[i] - cuttingLocation >= piecelength)
        {
            cnt++;
            cuttingLocation = v[i];
        }
    }
 
    // 목표 횟수로 자르고 남은 롤 케이크도 목표하는 크기이면 true를 반환
    if (cnt == givenCnt && l - cuttingLocation >= piecelength)
        return true;
 
    return false;
}
 
int Cut(int givenCnt, int length)
{
    //이분탐색 초기값
    int left = 1; // 최소 케이크 조각 길이
    int right = length; // 최대 케이크 조각 길이
 
    int result = 0; // givenCnt 회 자른 경우 가장 작은 조각 길이의 최댓값
    int mid;
 
    while (left <= right)
    {
        mid = (left + right) / 2;
 
        if(isValid(givenCnt, mid))
        {
            result = mid; // 가장 작은 조각의 최대 길이를 업데이트
            left = mid + 1;
        }
        else 
        {
            right = mid - 1;
        }
    }
 
    return result;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m >> l;
 
    v.resize(m);
    for(int i = 0; i < m; i++){
        cin >> v[i];
    }
 
    // 자르는 위치를 정렬. 해당문제는 굳이 정렬하지 않아도 된다.
    sort(v.begin(), v.end());
 
    for(int i = 0; i < n; i++){
        int givenCnt;
        cin >> givenCnt;
 
        cout << Cut(givenCnt, l) << "\n";
    }
 
    return 0;
}

 

 

 

 

---