[이분탐색] BOJ 1477 휴게소 세우기

import sys
input = sys.stdin.readline
 
N, M, L = map(int, input().split())
arr = [0] + list(map(int, input().split())) + [L] # ...!! 0과 끝값까지 고려를 해야한다..! 
arr.sort()
 
def bin_search(arr):
    start, end = 1, L 
    answer = 0
    while start <= end:
        cnt = 0
        mid = (start + end) // 2
        
        for i in range(1, len(arr)):
            if arr[i] - arr[i-1] > mid:
                cnt += (arr[i] - arr[i-1] - 1) // mid # -1을 안하면 휴개소 포함
                
        if cnt > M:
            start = mid + 1 
        else:
            answer = mid 
            end = mid - 1
            
            
    return answer
 
 
print(bin_search(arr))