🔥

문제

집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ⋯, xN이고, 집의 좌표는 모두 다르다.

윌리는 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 설치할 때, 가장 인접한 두 공유기 사이의 거리의 최댓값을 구해보자.

입력

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

출력

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

예제 1 입력

5 3
1 2 8 4 9

예제 1 출력

3

Source

N, C = map(int, input().split())

house = list(map(int, input().split()))
house.sort()

l = 0
r = 1000000000
answer = 1000000000

while(l <= r):
	# m: 공유기 사이의 거리
    m = (l + r) // 2

    prev = house[0]
    cnt = 1
    for i in range(len(house)):
        if(house[i] - prev >= m):
            prev = house[i]
            cnt += 1

    if(cnt >= C):
        l = m + 1
    else:
        r = m - 1

print(l - 1)

참고