레이스( BOJ 1508 )

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

1508번: 레이스

 

문제 파악하기

M명의 심판을 배치하는 여러 가지 경우 중, 가장 가까운 심판 사이의 거리가 최대인 경우를 구하는 문제입니다. 만약 모든 경우의 수를 조사한다면, 최악의 경우 1,000,000개 자리 중 50명의 심판을 배치하는 모든 가짓수를 조사해야 합니다. 터무니없이 많기 때문에 문제를 조금 바꿀 필요가 있습니다. 문제를 최적화 문제에서 결정문제로 바꿔봅시다.

 

문제 해결하기

결정 문제란 현재 조건을 만족하는 정답이 있는지 없는지 판단하는 문제를 의미합니다. 우리는 이 문제를 [ 심판과 심판 사이의 최소 거리를 d라고 할 때, M명의 심판을 배치할 수 있는가? ]로 바꿀 수 있습니다. 만약 M명의 심판을 배치할 수 있다면 어떨까요? 이 경우, d보다 작은 값들은 모두 M명의 심판을 배치할 수 있다고 판단할 수 있기에 d보다 큰 값을 다시 살펴보면 됩니다. 반대로, 만약 M명의 심판을 배치할 수 없다면 어떨까요? 이번에는 d보다 큰 값들은 모두 M명의 심판을 배치할 수 없다고 판단할 수 있기에 d보다 작은 값을 탐색하면 됩니다. 이렇게 d의 값에 따라 탐색하는 범위를 점차 줄여가면 문제를 해결할 수 있으며, 가장 효율적으로 범위를 줄이기 위해선 이분 탐색을 활용할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 55
using namespace std;
 
int N, M, K;
int inp[NMAX];
 
int l, r, mid, pos;
int cnt, bef, dist;
vector< int > ans;
 
int main() {
    // input
    scanf("%d %d %d", &N, &M, &K);
    for(int i=1;i<=K;i++) scanf("%d", &inp[i]);
 
    // 이분 탐색
    l = 0;
    r = inp[K]-inp[1];
    while(l<=r) {
        mid = (l+r)/2;
 
        bef = inp[1];
        cnt = 1; pos = 2;
        while(pos<=K) {
            if(inp[pos]-bef < mid) pos++;
            else {
                cnt++;
                bef = inp[pos++];
            }
        }
 
        if(cnt < M) r = mid-1;
        else {
            dist = max(dist, mid);
            l = mid+1;
        }
    }
 
    cnt = 1;
    bef = inp[1];
    ans.push_back(1);
    for(pos=2;pos<=K;pos++) {
        if(inp[pos]-bef < dist) ans.push_back(0);
        else {
            if(cnt == M) ans.push_back(0);
            else {
                ans.push_back(1);
                
                cnt++;
                bef = inp[pos];
            }
        }
    }
 
    for(int i=0;i<K;i++) printf("%d", ans[i]);
    
}

후기

파라메트릭 서치(매개 변수 탐색)의 대표적인 유형입니다. 다만, 이 문제에서는 심판의 모습을 구해야하기 때문에 파라메트릭 서치를 배우고 연습하는 사람에게 딱 적합한 문제라고 생각합니다.