[C++] 백준/BOJ - 1477 : 휴게소 세우기

문제 이해 단계

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

1477번: 휴게소 세우기

입력으로 가지고 있는 휴게소 N과 만들어야 할 휴게소 M, 고속도로 길이 L이 주어진다.

휴게소를 M개를 더 지어 휴게소 사이의 거리를 최소화하려고 한다.
고속도로 끝과 중복된 곳에 배치하는 것은 금지한다.

휴게소들 사이의 거리가 최소가 되도록 이상적으로 배치했을 때,
그중 구간의 길이가 가장 긴 것을 출력하는 문제

 

---

문제 접근 단계

문제가 말을 어렵게 써놔서 이해하는 게 한참 걸렸다.

이 문제의 제한 범위를 보면, 고속도로의 길이는 최대 1000까지만 가능하다.

그리고 N과 M의 범위는 각각 50,100으로
시간초과는 걱정하지 않아도 될 정도이다.

M개의 휴게소를 모두 세워서 최소 거리를 만들어야 하기 때문에
두 휴게소 사이에 몇 개의 휴게소를 세워야 하는지가 중요하다.

당연히 두 휴게소 사이의 길이가 긴 것을 우선적으로 새로운 휴게소를 세워야 한다.

근데 얼마큼?
2 등분하는 게 좋을 수도 있고, 3등분하는 게 좋을 수도 있다.

이는 뒤에 있는 다른 휴게소의 거리에 따라 달라지는 것이다.
이를 모든 경우의 수에 대해 해 본다는 것은 너무나 복잡하다.

차라리 고속도로의 길이가 1000까지밖에 안되니까
이걸 1000번 살펴보는 게 더 나을 수도 있다.

여기서 이분탐색 아이디어가 나왔다.

절반씩 딱 끊어가면서 하면
탐색도 훨씬 빠르게 답을 구할 수 있을 것이다.

---

탐색하는 기준

이분탐색을 해야 하는 것은 알겠다.
근데 뭘 기준을 잡고 해야 하지?

이 문제의 핵심은, M개의 휴게소를 세워 거리를 최소로 배치하는 것이다.
그리고 그때의 가장 긴 길이가 얼마인지 구하는 것이다.

여기서 M개의 휴게소들이 두 휴게소 사이에서 지어지는데도 거리 간격이 존재한다.
그리고 그 간격에 따라 지어지는 개수도 달라질 것이다.

만약 휴게소 하나당 3씩 띄어서 짓는다고 하자.

그럼 10 ~ 50 사이에는 총 40 / 3 = 13개를 지을 수 있다.

개수를 늘려 휴게소 하나당 6씩 띄어서 짓는다면?
40 / 6 = 6개밖에 짓지 못한다.

그런데 우리가 지어야 할 휴게소는 M개로 딱 맞아떨어져 야한다.

즉, 총개수를 셌을 때, 개수가 모자라다면 휴게소 사이의 거리를 줄이고,
개수가 M개보다 많다면 휴게소 사이의 거리를 늘리는 식으로 이분탐색을 진행할 수 있다.

자세한 것은 코드로 살펴보는 것이 빠르다.
추가적인 설명 또한 문제 구현 단계에서 살펴보겠다.

 

---

문제 구현 단계

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    int N,M,L;
    cin >> N >> M >> L;

    vector<int> v(N);
    for(int i = 0; i < N; i++) cin >> v[i];

    // 거리 차를 구하기 위해 시작 위치와 끝 위치를 추가
    v.push_back(0);
    v.push_back(L);
    sort(v.begin(),v.end()); // 오름차순 정렬

    int start = 1;
    int end = L-1; // 고속도로 끝에는 못지음
    int mid;
    int ans = 9999;

    // 이분탐색 시작
    while(start <= end){
        mid = (start+end)/2;
        int count = 0; // 현재 지은 휴게소 갯수
        // 두 휴게소 사이의 거리 차
        for(int i = 1; i < v.size(); i++){
            int len = v[i] - v[i-1];

            int cnt = len / mid; // 두 휴게소 사이에 지을 수 있는 휴게소 개수
            if(cnt > 0){
                // 딱 맞아떨어진다는 것은 마지막 휴게소와 겹쳤다는 뜻이므로 하나 빼줌
                if(len % mid == 0) count += cnt-1;
                else count+=cnt;
            }
        }
        if(count > M) start = mid+1; // 개수가 M보다 많으므로 간격 넓혀줌
        else{
            // 개수가 M보다 적으므로 간격 줄여줌
            end = mid-1;
            // M개의 휴게소 간격이 모두 일정할 순 없음
            // 우리가 구하고자 하는 것은 최소한의 경우 중 가장 긴 것
            ans = min(ans,mid);
        }
    }
    cout << ans;
}

전체 코드이다.

이분탐색 전에 코드에서 봐야 할 것은, 정렬을 하기 전에 벡터 v에 0과 L을 추가시킨 것이다.

이는 (0, 첫 휴게소), (마지막 휴게소, 고속도로 끝)도 포함돼야 하기 때문이다.

그리고 이분탐색을 시작하면  
len/mid를 하는 것으로 들어갈 수 있는 최대 개수를 구한다.

cnt는 현재 들어갈 수 있는 휴게소의 개수이다.

여기서 len % mid == 0 일 때, 1을 빼주는 것이 의아할 텐데, 
이는 중복 때문에 그렇다.

예를 들어, (10,50) 사이에 간격이 10인 휴게소를 세운다고 하면,
계산 상으로는 40/10 = 4이 나와야 한다.

그런데 이미 50에는 휴게소가 지어져 있다.
그래서 사실상 (20,30,40) 이렇게 3개가 나와야 하는 것이다.

4개가 나오기 위해서는 51이 되어야 한다.
그래야지만 (20,30,40,50,51)로 중복이 일어나지 않는다.

마지막으로 ans = min(ans, mid)에 관한 설명인데,
여기서 특이한 점은 휴게소의 개수가 M 이하일 때도 정답일 수도 있다는 것이다.

이는 우리가 계산할 때 휴게소를 일정 간격으로 두고 했다.

이는 휴게소 사이의 거리가 일정하지 않을 수도 있기 때문에
일정 간격으로 두는 것으로 M개가 나오지 않을 수도 있다.

그렇기 때문에 최소한의 경우 중 가장 긴 것을 구하는 것이다.

 

---

시행착오

처음에는 우선순위 큐로 풀었다.

우선순위큐인 거 확신했는데, 아니었다.
역시 문제 유형을 모르고 풀면 너무 어렵다.

문제 힌트를 보고도 이분탐색으로 풀어보려고 했는데 전혀 감이 안 잡힌다.

그래서 포기하고 답을 봤는데...
와 이걸 어떻게 생각하지?

답을 보니까 알겠지 이거 나는 절대로 못 떠올릴 거 같은데..