1508번 레이스

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

비슷한 문제 : https://hsdevelopment.tistory.com/547

파라매트릭 서치(Parametric Search) Greedy 그리디 탐색 복습 필수 추천 코테 코딩

#include<bits/stdc++.h>
 
using namespace std;
 
int n, m, k, ans;
vector<int> v;
 
bool chk(int mid)
{
    int cnt = 0, pos = -1;
 
    for (int i = 0; i < v.size(); i++) {
        if (pos <= v[i]) {
            ++cnt;
            pos = v[i] + mid;
        }
    }
 
    return cnt >= m;
}
 
void bt(int s, int e)
{
    for (int i = 0; i < 100; i++) {
        int mid = (s + e) / 2;
 
        // ans는 [mid, e]에 있다.
        if (chk(mid)) {
            s = mid + 1;
            ans = max(ans, mid); // 정답 길이(가장 가까운 두 심판관의 거리의 최댓값)
        }
        else {
            e = mid - 1;
        }
    }
}
 
int main()
{
    cin.tie(0);
    scanf("%d %d %d", &n, &m, &k);
 
    v.assign(k, 0);
    for (int i = 0; i < k; i++) {
        scanf("%d", &v[i]);
    }
 
    bt(0, v[k - 1]);
 
    // 최대 거리인 ans를 기준으로 출력한다.
    int here = -1, cnt = 0;
 
    for (int i = 0; i < v.size(); i++) {
        // 현재 위치와 v[i]의 위치 비교 및 심판관이 몇 명인지도 고려해준다.
        if (here <= v[i] && cnt < m) {
            printf("1");
            here = v[i] + ans;
            ++cnt;
        }
        else {
            printf("0");
        }
    }
 
    printf("\n");
 
    return 0;
}