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

문제 설명

문제 링크

고속도로 위에 N개의 휴게소들이 있고 M개의 휴게소를 새로 설치하여 휴게소들 사이의 최대 거리를 최소화하는 문제이다.

이미 존재하는 휴게소와 도로의 시작점, 끝점이 주어지고, 추가로 세울 수 있는 휴게소의 개수가 주어진다.

문제 풀이

이제는 익숙한 이분 탐색 문제이다. 다만 해당 문제의 까다로운 점은 특정 긴 구간을 찾아 균일하게 나누는 것이 아닌, 동적으로 변경되는 휴게소 거리에 따라 새 휴게소를 설치해야 한다는 점이다.

이를 위해 find_location 함수를 구현해주었다.

우선 기존의 이분 탐색과 같이 입력을 받은 후 정렬해준다. 이 때 시작점과 끝점도 고려해야 하기 떄문에 배열에 추가해준 후 정렬을 한다.

find_location함수는 휴게소 설치 가능 여부를 확인하는 역할을 하는데, 이분 탐색 함수 binary_search에서 받은 값으로 어느 지점에 설치해주어야 하는지 찾아본다.

binary_search에서 탐색 범위를 확인할 때의 mid값을 find_location으로 전달하여 이 구간을 어떻게 나눌지 확인해준다.

코드

import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())

def find_location(rest, dist, M):
    count = 0
    for i in range(1, len(rest)):
        count += (rest[i] - rest[i - 1] - 1) // dist
    return count <= M

def binary_search():
    lt = 1
    rt = L

    while lt < rt:
        mid = (lt + rt)//2
        if find_location(rest, mid, M):
            rt = mid
        else:
            lt = mid + 1
    
    return lt 

rest = list(map(int, input().split()))
rest.append(0)
rest.append(L)
rest.sort() 

print(binary_search())