[백준] 1477 - 휴게소 세우기

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

1477번: 휴게소 세우기

 

이 문제를 보자마자 파라메트릭 서치가 떠올랐다.

이분 탐색이라는 카테고리는 왜 필요한지 모르겠지만, 고속도로의 길이 L이 많이 커진다면 이분 탐색이 필요할 것이다.

 

하지만 100 <= L <= 1000이어서 완전 탐색도 해보았지만, 걸리는 시간은 0ms였다.

 

어떻게 풀어도 상관이 없는 문제이다.

 

파라메트릭 서치의 조건으로 휴게소가 없는 구간의 최댓값의 최솟값으로 정한다.

예제 입력 1에서, 70이라는 조건으로 생각해보자.

 

그리디 하게, 최대 70이라는 간격만 두고 휴게소를 설치한다고 가정하면,

[70, 82, 152, 201, 271, 341, 411, 481, 551, 555, 622, 692, 755] 이런 식으로 휴게소를 설치할 수 있다.

굵은 글씨로 쓴 것은 추가로 설치하는 휴게소의 위치이다.

 

70 미만으로 조건을 잡는다면 어떤 방식으로 설치해도 만족할 수 없다.

 

[완전 탐색 코드]

#include <iostream>
#include <algorithm>
using namespace std;
int a[52];
int main()
{
    int n, m, l;
    cin >> n >> m >> l;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    sort(a, a + n);
    a[n++] = l;
    int left = 1, right = a[0];

    for (int i = 1; i < n; i++)
    {
        right = max(right, a[i] - a[i - 1]);
    }
    int ans = 0;
    for(int mid = 1; mid <= right; mid++) {
        int cursor = 0;
        int cnt = m;
        for (int i = 0; i < n; i++)
        {
            if (a[i] - cursor <= mid)
            {
                cursor = a[i];
                continue;
            }
            else
            {
                cnt--;
                if (cnt < 0)
                {
                    break;
                }
                cursor += mid;
                i--;
            }
        }
        if (cnt < 0)
        {
            continue;
        }
        else
        {
            cout << mid;
            return 0;
        }
    }

    cout << ans;
}

 

[이분 탐색 코드]

#include <iostream>
#include <algorithm>
using namespace std;
int a[52];
int main()
{
    int n, m, l;
    cin >> n >> m >> l;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    sort(a, a + n);
    a[n++] = l;
    int left = 1, right = a[0];

    for (int i = 1; i < n; i++)
    {
        right = max(right, a[i] - a[i - 1]);
    }
    int ans = 0;
    while (left <= right)
    {
        int mid = (left + right) / 2;

        int cursor = 0;
        int cnt = m;
        for (int i = 0; i < n; i++)
        {
            if (a[i] - cursor <= mid)
            {
                cursor = a[i];
                continue;
            }
            else
            {
                cnt--;
                if (cnt < 0)
                {
                    break;
                }
                cursor += mid;
                i--;
            }
        }
        if (cnt < 0)
        {
            left = mid + 1;
        }
        else
        {
            if (ans == 0 || ans > mid)
            {
                ans = mid;
            }
            right = mid - 1;
        }
    }

    cout << ans;
}

 

L의 범위가 최대 1000이라서 둘의 성능 차이는 그렇게 크게 없는 듯하다.