백준 1477번 휴게소 세우기

🔒[문제 url]

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

🔑알고리즘

한 휴게소와의 거리를 기준으로 이분탐색을 진행한다.
임의의 거리 $k$에 대하여, 휴게소가 존재하지 않는 구간의 거리가 $k$이상이라면
휴게소를 (구간 거리) / k개만큼 설치할 수 있다.
이때, 이미 휴게소가 있는 곳에는 설치할 수 없으므로
(구간 거리) % k == 0이라면 설치 갯수는 (구간 거리) / k - 1이 된다.

휴게소간 최대 거리가 $k$가 되도록했을 때,
설치한 휴게소가 $m$개 이하라면 $k$를 줄이고
설치한 휴게소가 $m$개 초과라면 $k$를 늘려 재설치한다.

🐾부분 코드

while(left <= right)
{
    int mid = (left + right) / 2;

    int cnt = 0;//설치한 휴게소 갯수
    for(int i = 1; i <= n+1; i++)
    {
        int dist = v[i] - v[i-1];

        cnt += dist / mid;
        //설치하려는 곳에 이미 휴게소가 있다면
        if(dist % mid == 0) cnt--;
    }

	//설치한 휴게소가 m개 이하라면, 거리를 줄여본다.
    if(cnt <= m) ans = mid , right = mid - 1;
    else left = mid + 1;
}

<이분 탐색>
휴게소가 없는 구간의 길이가 mid를 초과하는 구간에 휴게소를 설치한다.
휴게소가 이미 있는 곳에 설치하지 않도록 주의한다.

🪄전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,m,l;
vector<int> v;

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> l;
    for(int i = 0; i < n; i++)
    {
        int x; cin >> x;
        v.push_back(x);
    }
}


void SOLVE()
{
	//휴게소의 위치는 [1 , l-1]이다.
    v.push_back(0); v.push_back(l);//v.size() == n+1
    //Sort for Binary Search
    sort(v.begin(),v.end());

    int left = 1 , right = l;

    int ans;
    while(left <= right)
    {
        int mid = (left + right) / 2;

        int cnt = 0;//설치한 휴게소 갯수
        for(int i = 1; i <= n+1; i++)
        {
            int dist = v[i] - v[i-1];

            cnt += dist / mid;
            //설치하려는 곳에 이미 휴게소가 있다면
            if(dist % mid == 0) cnt--;
        }

        //설치한 휴게소가 m개 이하라면, 거리를 줄여본다.
        if(cnt <= m) ans = mid , right = mid - 1;
        else left = mid + 1;
    }

    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

이분탐색임을 알고 풀어서 쉽게 봤다가 시간이 꽤 걸렸던 문제다.
(이분 탐색 + 매개 변수 탐색)은 어느정도 정형화된 문제이기에 며칠간 몰아서 풀어보면 좋을 것같다.