[ 1477 ] [ 이분 탐색 ] 휴게소 세우기

풀이 과정

---

문제

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같은 정수이다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

---

풀이 과정

---

1. 이분 탐색으로 정답을 찾는다.
   • 현재 휴게소 위치를 오름차순으로 정렬
   • 이분 탐색으로 구할 값을 휴게소의 구간 최댓값이라고 하고, 시작점을 0, 끝점을 L로 두고 중간값일 때, 휴게소가 몇개 세워질 수 있는지 구한다.
   • 휴게소의 개수를 구할 때, 이미 휴게소가 있는 곳에 휴게소를 또 세울수 없으므로 나누어 떨어지는 경우에는 -1을 해준다.
   • 현재 구간에서 세워야 하는 휴게소의 개수 => ((휴게소[i] - 휴게소[i-1]) // 구간 최댓값)
   • 세워야 하는 휴게소의 개수를 넘기는 경우에는 시작점을 중간값+1로 조정하고, 휴게소의 개수보다 작다면 정답을 저장해둔 뒤, 끝점을 중간값-1로 조정한다.
2. 정답을 출력한다.

• 이분 탐색을 진행할 때, 시뮬레이션을 어떻게 할지를 많이 고민해보아야 할 것 같음.

---

소스 코드

---

import sys

input = sys.stdin.readline
N, M, L = map(int, input().rstrip().split())
stations = list(map(int, input().rstrip().split()))
stations = [0] + stations + [L]
stations.sort()

left = 0
right = L
answer = 0
while left <= right:
    mid = (left + right) // 2

    # simulate
    add_count = 0
    for i in range(1, len(stations)):
        dist = stations[i] - stations[i-1]
        if dist > mid:
            add_count += (dist // mid)
            if dist % mid == 0:
                add_count -= 1
    if add_count > M:
        left = mid + 1
    else:
        answer = mid
        right = mid - 1

print(answer)