이번 문제는 이분 탐색을 통해 해결하였다. 여기서의 left는 가장 작을 수 있는 차이인 1로, right는 가장 클 수 있는 차이인 home[-1]-home[0]으로 선언하였다. 그리고 mid를 잡으며 이분 탐색을 통해 가장 인접한 두 공유기 사이의 최대 거리를 구한다. 여기서 mid가 바로 현재의 가장 인접한 두 공유기 사이의 최대 거리가 되는 것이다.

• n, m을 입력받는다.
• 정답을 저장할 변수 answer를 0으로 선언한다.
• 집들의 위치를 저장할 리스트 home을 선언한다.
• n번 반복하며 home을 입력받는다.
• home을 오름차순 정렬한다.
• left, right를 1, home[-1]-home[0]으로 선언한다.
• left가 right 이하일 동안 반복하는 while문을 돌린다.
  -> mid를 (left+right)//2로 선언한다.
  -> cur을 home[0]으로 선언한다.
  -> 카운팅 변수 cnt를 1로 선언한다.
  -> 1부터 home의 길이까지 반복하는 i에 대한 for문을 돌린다.
  --> 만약 home[i]가 cur+mid보다 크거나 같을 경우,
  ---> cnt를 1 증가시킨다.
  ---> cur을 home[i]로 갱신한다.
  -> 만약 cnt가 m보다 크거나 같을 경우,
  --> left를 mid+1로 갱신한다.
  --> answer를 mid로 갱신한다.
  -> 그 외의 경우,
  --> right를 mid-1로 갱신한다.
• answer를 출력한다.

Code

n, m=map(int, input().split())
answer=0
home=[]
for _ in range(n):
    home.append(int(input()))
home.sort()
left, right=1, home[-1]-home[0]
while left<=right:
    mid=(left+right)//2
    cur=home[0]
    cnt=1
    for i in range(1, len(home)):
        if home[i]>=cur+mid:
            cnt+=1
            cur=home[i]
    if cnt>=m:
        left=mid+1
        answer=mid
    else:
        right=mid-1
print(answer)