[백준 1477] 휴게소 세우기

문제

다솜이는 고속도로를 가지고 있으며 고속도로에는 현재 N개의 휴게소가 존재한다. 

휴게소의 위치는 고속도로의 시작점으로부터 얼만큼 떨어져 있는지로 주어지며 여기서 M개의 휴게소를 세우려고 한다.

이때 휴게소들의 구간별 길이 중 최댓값이 최소가 되기위한 간격을 구하라.

무조건 M개의 휴게소를 세워야하고 기존에 휴게소가 있는 위치와 끝에는 세울 수 없다.

 

입력

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

 

출력

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

---

접근

이분탐색을 어떻게 적용해야할지 생각해보았다.

가장 먼저 구해야하는 것이 휴게소들의 구간별 간격이기 때문에 중간값(mid)을 휴게소들의 간격이라고 정해보았다.

이후 해당 간격만큼 휴게소를 설치하는 것까지 생각을 했다. 

 

하지만 휴게소를 어떻게 설치할지 생각이 떠오르지 않았다.

다른 사람들의 풀이를 봤을 때 A와 B휴게소가 있을 때 A와 B 사이에 mid간격으로 몇 개의 휴게소를 세울 수 있는지 보고 휴게소를 세운 개수를 기준으로 left와 right값을 조절하였다.

 

구현

휴게소의 위치를 stations 리스트에 넣었으며 출발점 0과 고속도로의 끝에서 -1을 리스트에 추가했다.

고속도로 끝에는 휴게소를 설치할 수 없기 때문이다.

그리고 오름차순으로 정렬을 하였다.

N, M, L = map(int, input().split())
stations = list(map(int, input().split()))
stations.append(0)
stations.append(L-1)
stations = sorted(stations)

 

그리고 left=0, right=L-1로 하여 이분탐색을 시작하였다.

1번 인덱스부터 마지막 인덱스까지 탐색을 하여 [ 현재 인덱스 - 이전 인덱스]의 간격이 mid보다 클 때 휴게소를 세울 수 있는 것이고 해당 간격의 -1를 mid로 나눈 몫을 설치한 휴게소의 수인 count를 증가시킨다.

이때 -1을 빼는 이유는 이미 설치했던 곳에는 설치하면 안되기 때문이다.

 

휴게소를 설치하고 M보다 많이 설치했다면 설치하는 간격을 넓혀야하기 때문에 left를 mid+1로 갱신하고 그렇지 않다면 right를 mid-1로 한다. 그리고 이 부분에서 answer에 mid를 넣어 최종해를 구한다.

left = 0
right = L-1
while left <= right:
    mid = (left+right) // 2
    count = 0 # 설치한 휴게소의 수
    for i in range(1, len(stations)):
        if stations[i] - stations[i-1] > mid:
            count += (stations[i] - stations[i-1] -1)//mid

    if count > M:
        left = mid + 1
    else:
        answer = mid
        right = mid - 1

print(answer)

---

전체 코드

import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
stations = list(map(int, input().split()))
stations.append(0)
stations.append(L-1)
stations = sorted(stations)

left = 0
right = L-1
while left <= right:
    mid = (left+right) // 2
    count = 0 # 설치한 휴게소의 수
    for i in range(1, len(stations)):
        if stations[i] - stations[i-1] > mid:
            count += (stations[i] - stations[i-1] -1)//mid

    if count > M:
        left = mid + 1
    else:
        answer = mid
        right = mid - 1

print(answer)