[백준] 17128번 : 케이크 자르기 (C++)

17128번 : 케이크 자르기

---

문제)

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

예를 들어 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개 줄에 걸쳐 각 목록에 있는 횟수대로 롤 케이크를 잘랐을 때 가장 작은 조각의 길이의 최댓값을 출력한다.

 

 

 

풀이)

 

// 17179. 케이크 자르기
#include <iostream>
#include <vector>
 
using namespace std;
 
int c;
int n, m, l;
vector<int> vec;
 
bool check(int x)
{
    int cnt = 0;
    int s = 0;
 
    // x 크기에 맞추어 c번 잘랐을 때, 가능한지 체크
    for (int i = 0; i < vec.size() && cnt < c; i++)
    {
        if (vec[i] - s >= x)
        {
            cnt++;
            s = vec[i];
        }
    }
 
    return (cnt >= c) && (l - s >= x);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> l;
 
    for (int i = 0; i < m; i++)
    {
        cin >> c;
        vec.push_back(c);
    }
 
    for (int i = 0; i < n; i++)
    {
        cin >> c;
 
        int s = 1;
        int e = l;
 
        int ans = 0;
        while (s <= e)
        {
            int mid = (s + e) / 2;
 
            if (check(mid))
            {
                ans = mid;
                s = mid + 1;
            }
            else
            {
                e = mid - 1;
            }
        }
 
        cout << ans << '\n';
    }
 
    return 0;
}
 

---

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

17179번: 케이크 자르기