[백준] 1477 휴게소 세우기

문제 링크

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

접근 방법

휴게소 간의 거리의 거리의 최대값을 최소화 한 값을 출력해야 한다는 키워드에서 파라메트릭 서치임을 알 수 있다. 또한 고속도로의 끝과 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없다는 제한조건이 존재한다. 파라메트릭 서치에서 가장 중요한 것은 무엇을 기준으로 탐색을 진행 할 것인가? 인데, 이 문제에서는 이미 존재하고 있고 새로운 휴게소를 건설할 수 없는 지점(휴게소)가 있기 때문에 휴게소와 휴게소 사이의 거리를 사용한다.

코드 설명

rest_areas : 현재 휴게소와 고속도로의 시작과 끝을 넣어준다. -> 1번째 원소에서 0번째 원소를 뺼 경우 출발지점에서 첫번쨰 휴게소 사이의 거리를 알 수 있다. 이를 반복하면 모든 휴게소 사이의 거리를 알 수 있다.

코드

rest, more_rest, highway_len = map(int, input().split())
rest_areas = [0] + list(map(int, input().split())) + [highway_len]
rest_areas.sort()

left = 1
right = highway_len - 1
mn = 99999
while left <= right:
    mid = (left + right) // 2
    count = 0

    for i in range(1, len(rest_areas)):
        if rest_areas[i] - rest_areas[i - 1] > mid and rest_areas[i] - rest_areas[i - 1] - 1 > 0:
            count = count + (rest_areas[i] - rest_areas[i - 1] - 1) // mid

    if count > more_rest:
        left = mid + 1

    else:
        right = mid - 1
        if mn > mid:
            mn = mid

print(mn)