백준 17179 케이크 자르기

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

17179번: 케이크 자르기

 

케이크를 자를건데 자를 수 있는 M가지 지점이 있고 Q번 잘랐을때 가장 작은 조각의 길이를 최대화 하는 문제입니다.

 

완전탐색부터 접근을 해봅시다.

 

가장 떠올리기 쉬운 완전탐색 접근은 "가장 작은 조각이 Xcm이상일때 자르는 것이 가능한가"에 대해 모든 2 ~ L까지 해보는 것입니다.

 

모든 2 ~ L에 대해 확인하며 잘라본다면 특정 시점부터 불가능한 지점이 나올것이고, 직전 지점이 정답일 것입니다.

 

완전탐색을 위 방법 그대로 시도한다면 시간초과입니다.

 

위와 같은 완전탐색 접근을 하면서 특정 시점부터 불가능한 지점  이라는 관찰을 통해 정답이 단조성을 띈다는 것을 알 수 있습니다.

 

정답이 단조성을 띄기 때문에 이분탐색을 통한 최적화가 가능합니다.

 

code(c++)

#include <bits/stdc++.h>

#define endl "\n"
#define NM 303030
#define MAX 101010
#define BIAS 1048576
#define MOD 20170805
#define X first
#define Y second
#define INF 0x3f3f3f3f
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, m, l;
int arr[1111];

tuple<int, int> ok(int x){
    int cnt = 0;
    int prev = 0;
    for (int k = 0 ; k <= m; k++){
        if (arr[k] - prev >= x){
            cnt++;
            prev = arr[k];
        }
    }
    return {cnt, x};
}

void input() {
    cin >> n >> m >> l;
    for (int i = 0; i < m; i++) cin >> arr[i];
    arr[m] = l;
}

void pro() {
    for (int i = 0 ; i < n ; i++){
        int x;
        cin >> x;
        int s = 0;
        int e = arr[m - 1];
        int ans = 0;
        while (s <= e){
            int mid = s + e >> 1;
            auto [cnt, tmp] = ok(mid);
            if (cnt > x){
                s = mid + 1;
                ans = max(ans, tmp);
            }else{
                e = mid - 1;
            }
        }
        cout << ans << endl;
    }
}

int main() {
    fastio;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    input();
    pro();
    return 0;
}