[BOJ/백준] 6209 제자리 멀리뛰기

import sys
 
input = sys.stdin.readline
 
D,N,M = map(int,input().split())
 
arr = [0]+[int(input()) for _ in range(N)]
 
arr.sort()
arr.append(D)
left = 0
right = D
ans = float('inf')
while left<=right:
    mid = (left+right)//2
    cnt = 0
    post_ind = 0
    for ind in range(1,N+2):
        if arr[ind] - arr[post_ind] <= mid:
            cnt += 1
        else:
            post_ind = ind
    
    if cnt > M:
        right = mid -1
    else:
        left = mid + 1
 
print(left)

 

import sys
input = sys.stdin.readline
 
D,N,M = map(int,input().split())
 
 
arr = [D] + [int(input()) for _ in range(N)]
 
arr.sort()
left = 0
right = D
ans = 0
while left<=right:
    mid = (left+right)//2
    past_island = 0
    cnt = 0
    for island in arr:
        if island - past_island >= mid:
            cnt += 1
            past_island = island
    
    if cnt >= N-M+1:
        ans = max(ans,mid)
        left = mid + 1
    else:
        right = mid -1
 
print(ans)