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

• 문제 : https://www.acmicpc.net/problem/1477
• 이분탐색

 

n, m, l = map(int, input().split())
li = list(map(int, input().split()))
li.append(0)    # 처음
li.append(l)    # 끝
li.sort()

dist = []   # 휴게소 사이의 거리를 담을 배열

for i in range(1, len(li)):
    dist.append(li[i]-li[i-1]-1)    # 시작이 1부터라서 거리 구하고 1을 뺀다
dist.sort()

l, r = 1, l
answer = 1001

while l <= r:   # 이분탐색
    mid = (l + r) // 2
    cnt = 0

    for i in dist:
        cnt += i // mid # 거리들을 mid값으로 나눈 몫을 카운트
    
    if cnt > m:     # 개수가 많으면
        l = mid + 1     # 크기를 늘린다.
    else:   
        answer = min(answer, mid)   # 가능한 값 중 최소값으로 업데이트
        r = mid - 1 # 개수가 적으면 크기를 줄인다.

print(answer)