BOJ 1477번: 휴게소 세우기

문제

문제 바로가기> BOJ 1477번: 휴게소 세우기

1477번: 휴게소 세우기

 

풀이

M개의 휴게소를 가능한 빈 공간에 모두 세워보는 조합 방식으로는 너무 많은 경우의 수가 있다.

따라서 입력 받은 위치를 정렬하고, "각 휴게소 간 거리 중 최대값"으로 이분 탐색하여 문제를 해결하였다.

( + 거리이기 때문에 low 값을 0이 아닌 1로 설정하였다.)

문제를 풀기 전에 "예제 입력 1"을 손으로 그려보고 문제를 푸니, 문제를 금방 풀 수 있었던 거 같다.
문제를 이해하고, 코딩을 시작하기 전에, 꼭 한번 예제를 손으로 풀이해 보는 시간을 갖는 게 좋은 것 같다!!
이렇게 한 후로 많은 실수를 줄일 수 있게 된 것 같음!!

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

int N; // 현재 휴게소의 개수
int M; // 더 지을 휴게소 개수
int L; // 고속 도록 길이
int restArea[MAX]; // 현재 휴게소 위치

void input(){
    cin >> N >> M >> L;
    for(int i=0; i<N; i++) cin >> restArea[i];
}

bool check(int val){
    
    int cur=0, idx=0, cnt=0;

    // 세워진 휴게소 확인
    while (idx < N){
        while(cur+val < restArea[idx]){
            cur += val;
            cnt++;
        }
        cur = restArea[idx++];
    }

    // 고속도로 끝까지 확인
    while(cur+val < L){
        cur+=val;
        cnt++;
    }

    return cnt <= M;
}

void solve(){

    // 1. 현재 휴게소 위치 정렬
    sort(restArea, restArea+N);

    // 2. 이분 탐색
    int low=1, mid, high=L;
    while (low <= high){
        mid = (low+high)/2;
        if(check(mid)) high = mid-1;
        else low = mid+1;
    }

    // 3. 휴게소가 없는 구간의 최댓값의 최솟값
    cout << low;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solve();
}