이분탐색은 "정렬된 리스트"에서 "특정값"을 찾을 때 쓴다.

풀이

두 공유기 사이 최소거리의 최대값 = 특정값 으로 생각한다면
정렬된 리스트 = 두 공유기 사이 최소 거리 후보군 으로 생각할 수 있다.

문제를 예로 들면, 집 좌표는 아래와 같다.

1 2 4 8 9

이 때 공유기를 가장 짧게 설치하면 거리가 1이고 가장 길게 설치하면 거리가 (9-1) = 8이다.

따라서, 정렬된 리스트 = [1,2,3,...,8]이다.

우리는 위 리스트에서 문제 조건을 만족하는 최대값을 찾으면 된다.

binary_search

mid를 정답(두 공유기 사이 최소거리의 최대값)으로 가정하고 로직을 탄다.

두 집 사이의 거리가 mid보다 크면 공유기를 설치한다.

만약 공유기 개수가 남으면 정답을 낮춰야 한다.(공유기를 더욱 촘촘하게 설치해야 하니까)

공유기 개수가 남지 않는다면 공유기를 더욱 넓게 설치할 수 있다는 뜻이니까 정답을 높인다.

코드

import sys
input = sys.stdin.readline

def binary_search(lst):
    dist = 0
    start = 1
    end = lst[-1]-lst[0]
    
    while start<=end:
        mid = (start+end)//2
        cnt = 1
        cur = lst[0]
        
        for x in lst:
            if x-cur >= mid:
                cnt += 1
                cur = x
        
        if C > cnt:
            end = mid-1
        else:
            start = mid+1
            dist = mid
    return dist

if __name__ == '__main__':
    N,C = map(int,input().split())
    house = []
    for _ in range(N):
        house.append(int(input()))
    house.sort()
    print(binary_search(house))