[Python/파이썬] 백준 1477번 휴게소 세우기

 

문제

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

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

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

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

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

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다.

출력

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

 

제한

• 0 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• 100 ≤ L ≤ 1,000
• 1 ≤ 휴게소의 위치 ≤ L-1
• N+M < L
• 모든 휴게소의 위치는 중복되지 않음
• 입력으로 주어지는 모든 수는 정수

 

 

코드

처음에 생각했던 코드

from heapq import heappush, heappop, heapify

n, m, l = map(int, input().split())
rest = [0] + sorted(list(map(int, input().split())))
    
gap = [-(rest[i]-rest[i-1]) for i in range(1, len(rest))]  # 휴게소들 사이 간격
heapify(gap)

for _ in range(m):
    biggest = -heappop(gap)
    a, b = biggest//2, biggest-biggest//2
    heappush(gap, -a)
    heappush(gap, -b)
print(-heappop(gap))

heap 자료구조를 이용하여 휴게소 간 거리가 가장 큰 것들을 pop해서 그 절반 자리에 휴게소들을 설치하며 진행하려 했었다. 근데 해보니 예제도 안 되고 이렇게 푸는게 아닌거 같아서 찾아보니 이분탐색을 이용해서 풀면 된다고 해서 다음과 같이 풀이하였다.

 

정답 코드

n, m, l = map(int, input().split())
rest = [0] + sorted(list(map(int, input().split()))) + [l]

start, end = 1, l
ans = 0
while start <= end:
    cnt = 0
    mid = (start+end)//2
    
    for i in range(1, n+2):
        gap = rest[i] - rest[i-1]
        if gap > mid:   # 현재 mid 값보다 휴게소 간 거리가 멀다면 휴게소 설치
            cnt += (gap-1) // mid   # 현재 설치된 휴게소들은 제외해야 하므로 -1
            
    if cnt > m: # 설치하려는 개수보다 더 설치가 필요한 경우 거리를 늘려야 함
        start = mid + 1
    else:
        end = mid - 1
        ans = mid
        
print(ans)

이미 설치된 휴게소들의 위치를 rest에 저장해주는데 고속도로의 시작점과 끝점도 고려해주어야하므로 0과 l을 rest 배열에 추가해주어야 한다.

그리고 범위를 [1, l]로 잡고 이분탐색을 한다. 이때 시작범위를 0으로 잡으면 mid 값이 0이 될 수 있어 ZeroDivision 에러가 발생한다.

휴게소가 없는 구간의 최댓값을 mid로 볼 때 현재 설치된 휴게소의 간격이 mid보다 크다면 그 사이에 휴게소들을 설치해주어야 한다. 설치되는 휴게소의 개수는 (rest[i] - rest[i-1] - 1) // mid개이다. -1을 해주는 이유는 이미 설치된 양쪽의 휴게소들은 제외해야 하기 때문이다. 고속도로의 시작점과 끝점도 휴게소를 설치할 수는 없으므로 제외된다. 이렇게 모든 휴게소들에 대해 설치해야하는 휴게소의 개수를 세서 우리가 설치하려는 휴게소의 개수 m보다 크다면 설치 간격이 너무 좁아서 많이 설치된다는 말이므로 탐색 시작점(start)을 mid+1로 갱신해준다. 그렇지 않다면 탐색 끝점(end)를 mid - 1으로 갱신하고 이때의 mid 값을 ans에 저장해준다.