공유기 설치

💻 입력 조건

• 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

💻 출력 조건

• 첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

💻 입력 예시

5 3
1
2
8
4
9

💻 출력 예시

3

📖 문제 해결
가능한 집의 좌표의 범위가 10억이기 때문에 '가장 인접한 두 공유기 사이의 거리를' 이진 탐색을 이용하여 찾고자 하였습니다.
가장 인접한 두 공유기 사이의 거리가 최소(start) 1부터 최대(end) house[-1] - start 라고 설정한 후, 중간 지점의 값을 mid 변수에 저장합니다.
이 mid 변수의 값만큼의 최소 거리를 두고 공유기를 설치해 보았을 때 만약 공유기가 c개 이상 설치가 된다면 start = mid + 1로 설정하여 gap의 값을 늘려 탐색을 다시 시작합니다. 탐색을 다시 시작할 것이라 하더라도, 이 mid 거리만큼 떨어져서 공유기를 설치하였을 때 c개 이상 설치할 수 있기에 이 mid 값을 gap 변수에 저장합니다.
위와는 다르게 만약 c개 미만의 공유기만 설치할 수 있다면 end = mid - 1 로 설정하여 gap을 줄여 탐색을 다시 시작합니다.
이러한 반복적인 탐색은 start <= end 이 만족할 때까지 진행함으로써 적절하게 이진 탐색을 수행할 수 있도록 하였습니다.

# n, c 입력받기
n, c = map(int,input().split())

# 집의 위치 입력받기
house = []

for i in range(n):
    house.append(int(input()))
    
house.sort()

# 이진 탐색으로 적절한 gap을 찾기 위해 start와 end를 설정
start = 1
end = house[-1] - house[0]

while start <= end:
    
    mid = (start + end) // 2
    count = 1
    
    # 최소 mid의 gap을 가지도록 공유기를 설치해 보기
    value = house[0]
    for i in range(n):

        if house[i] >= value + mid:
            value = house[i]
            count += 1

    # c개 이상의 공유기를 설치할 수 있다면 gap을 늘리기
    if count >= c:
        start = mid + 1
        gap = mid

    # c개 미만의 공유기만 설치할 수 있다면 gap을 줄이기
    else:
        end = mid - 1
        
print(gap)