이분 탐색 - 2110번: 공유기 설치

가능한 공유기 간 거리를 이분 탐색으로 찾아야 시간초과되지 않음

n, c = map(int, input().split())
houses = []

for _ in range(n):
    line = int(input())
    houses.append(line)

houses.sort() # 오름차순 정렬!


# 공유기 사이 거리가 x이상일 때의 설치 가능한 공유기 수 확인하는 함수
def router_cnt(x):
    cnt = 1
    pos = houses[0]

    for i in range(1, n):
        if cnt >= c: # cnt가 c 이상이 되면 더 볼 필요 없으니 끝내기
            break
        if houses[i] - pos >= x:
            cnt += 1
            pos = houses[i]
        
    
    return cnt


left = 1 # 최소 공유기 간 거리
right = houses[-1] - houses[0] # 최대 공유기 간 거리

max_dist = 0 # 출력할 정답 (가능한 최대 공유기 간 거리)


while left <= right:
	# 현재 탐색 범위(left ~ right)를 둘로 쪼개는 중앙값 mid 구하기
    mid = (left + right) // 2

    res = router_cnt(mid) # mid 거리로 시도

    if res >= c: # mid 거리로 시도해본 결과가 c와 같거나 크다면, 현재 mid를 기준으로 오른편(더 큰 거리)으로 탐색 범위를 좁힘
        left = mid + 1
        max_dist = mid
    else: # mid 거리로 시도해본 결과가 c보다 작다면, 현재 mid를 기준으로 왼편(더 작은 거리)으로 탐색 범위를 좁힘
        right = mid - 1
    
    

print(max_dist)