[Python] BOJ 1477 - 휴게소 세우기

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

1477번: 휴게소 세우기

 

1. 고속도로 끝과 이미 설치된 곳에 휴게소를 세우지 못하므로 휴게소 위치를 입력받아

    rest배열에 넣은다음 처음과 끝 위치도 추가해준 뒤 정렬해준다.

 

2. count함수: 휴게소가 세워진 위치 사이를 이분탐색을 통해 구한 mid값으로 나눈 값들을 cnt에 저장한다.

                               cnt가 M보다 같거나 작으면 True를 리턴, M보다 크면 False를 리턴해준다.

 

3. lo = 0, hi = L+1을 넣고 이분탐색을 실행한다.

   count(mid)가 True라면, 즉 현재 간격으로 휴게소를 추가 설치했을 때, 추가 설치한 휴게소 갯수가

   M이하라면, 간격을 더 줄이고, count(mid)가 False이면 간격을 늘린다.

 

4. 휴게소가 없는 구간의 최댓값의 '최솟값' 을 구하고자 하는 것이므로 간격을

     False가 나오기 전까지 최대한 줄여본다. 그리고 그 최솟값은 최종적으로 lo에 있을 것이다.

     따라서 lo를 마지막에 출력해준다.

 

import sys
input = sys.stdin.readline
N, M, L = map(int, input().split())
rest = list(map(int, input().split()))
rest.append(0)
rest.append(L)
rest.sort()

def count(x):
    cnt = 0
    for i in range(1, N+2):
        cnt += (rest[i] - rest[i - 1] - 1) // x
    return cnt <= M

lo, hi = 0, L+1
while lo != hi:
    mid = (lo + hi) >> 1
    if count(mid):
        hi = mid
    else:
        lo = mid + 1

print(lo)

(solved.ac 티어: 골드 4)

 

# 이렇게 mid값을 직접 찾지않고 최댓값, 최솟값을 찾는 방법, 특정 범위를 좁혀나가는 목적으로

   이진 탐색을 사용하는 방법을 Parametric Search(매개변수 탐색)이라고 한다.

 

# https://www.acmicpc.net/problem/3079

'입국심사' 문제도 풀어보면 좋을 듯 하다.