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

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

1477번: 휴게소 세우기

문제 해결

• 전형적인 휴개소를 짓고 난 후의 휴게소가 없는 구간의 최댓값의 최솟값을 이분탐색으로 찾는 문제
• 길이를 조절해가며 대입했을 때 알맞은 길이를 찾는 문제이다.

 

CODE

n,m,l = map(int, input().split())
A = [0]+list(map(int, input().split()))+[l]
A.sort()
start = 1
end = l-1
answer = 0
while start <= end:
    cnt = 0
    mid = (start+end)//2
    for i in range(1,len(A)):
        if A[i] - A[i-1] > mid:
            cnt += (A[i]-A[i-1]-1)//mid
    if cnt >m:
        start = mid + 1
    else:
        end = mid -1
        answer = mid
print(answer)