[ BOJ / C++ ] 1477번 휴게소 세우기

이번 문제는 이분탐색으로 해결하는 문제였다. 처음에는 이분탐색으로 해결하는 방법이 생각이 안나서 이분탐색을 빼고 생각해보았다.

• 각 휴게소 간의 거리 배열 dis를 만든다.
• dis를 내림차순으로 정렬한다.
• 가장 큰 거리를 반으로 자른다. (휴게소를 사이에 세운다.)
• dis를 다시 내림차순으로 정렬한다. 이 과정을 m번 반복한다.

이 방식의 문제점은 가장 큰 거리를 반으로 나눴을 때도 그 나눈 거리가 가장 큰 거리일 때 발생한다. m이 부족하다면 남은 거리를 나누지 못하게 되어 최대거리가 커지게 된다.

이분탐색으로 해결할 수 있는 방식을 다시한번 생각해보았고, 구글의 힘을 조금 빌려 문제를 해결할 수 있었다.

• 각 휴게소 간의 거리 배열 dis를 만든다.
• dis를 내림차순으로 정렬한다.
• 이분탐색을 하는데, front에 1을, back에 l-1을 대입하고 시작한다. 다른 이분탐색과 다른점은 while문의 조건이 front<back-1이라는 점이다.
• 만약 mid가 dis보다 작은 경우 dis가 mid에 나눠 떨어지는지 확인하고, 나눠떨어진다면 cnt에 dis/mid-1을 더해주고, 나눠 떨어지지 않는다면 dis/mid를 더해준다. 매 루프마다 나오는 mid값이 휴게소 간 거리의 최대값이 되기 때문에 dis/mid-1 혹은 dis/mid개의 휴게소를 설치하는 것을 구현한 것이다.
• mid와 dis를 비교하고 난 뒤에 cnt와 m을 비교한다. cnt가 m보다 크다면 front에 mid를 넣어주고, cnt가 m보다 작으면 back에 mid를 넣어준다. 어떻게 보면 구간을 나누는 과정이기 때문에 mid-1이나 mid+1을 대입하지 않는다. (이 때문에 while문의 조건문도 front<back-1이 된다.)
• 이분탐색은 back에 저장된 값을 반환한다.

#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;

int n, m, l;
int point[MAX];
int dis[MAX];

void Input(){
    cin>>n>>m>>l;
    for(int i=0; i<n; i++){
        cin>>point[i];
    }
    sort(point, point+n);
}

void GetDistance(){
    dis[0]=point[0];
    for(int i=1; i<n; i++){
        dis[i]=point[i]-point[i-1];
    }
    dis[n]=l-point[n-1];
}

int BinarySearch(){
    int front=1;
    int back=l-1;
    while(front<back-1){
        int mid=(front+back)/2;
        int cnt=0;
        for(int i=0; i<=n; i++){
            if(dis[i]>mid){
                if(dis[i]%mid==0){
                    cnt+=dis[i]/mid-1;
                }
                else{
                    cnt+=dis[i]/mid;
                }
            }
        }
        if(m<cnt){
            front=mid;
        }
        else{
            back=mid;
        }
    }
    return back;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    GetDistance();
    cout<<BinarySearch()<<endl;
    return 0;
}