[인프런] 마구간 정하기

---

문제설명

N개의 마구간이 수직선 상에 있다. 각 마구간은 $x_1, x_2, x_3, \ ..., \ x_N$의 좌표를 가지며 마구간 간에 좌표가 중복되는 일은 없다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않는다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶어한다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성해라.

입력조건

• 첫 줄에 자연수 N(3 <= N <= 200,000)과 C(2 <= C <= N)가 공백을 사이에 두고 주어진다.
• 둘째 줄부터 N개의 줄에 걸쳐 마구간의 좌표 $x_i$(0 <= $x_i$ <= 1,000,000,000(10억))가 한 줄에 하나씩 주어진다.

출력조건

• 첫 줄에 가장 가까운 두 말의 최대거리를 출력해라.

사고과정

• 예전에 풀어본 '공유기' 문제와 비슷한 유형이었다. 주어진 데이터 범위가 10억으로 매우 크기 때문에 시간복잡도 $logN$이 걸리는 이분탐색을 활용한 결정 알고리즘을 활용했다.

풀이

n, c = map(int, input().split())
arr = [int(input()) for _ in range(n)]
arr.sort()

start = 1
end = arr[-1] - arr[0]
while start <= end:
    mid = (start + end) // 2
    count = 1
    prev = arr[0]
    for a in arr[1:]:
        if prev + mid <= a:
            count += 1
            prev = a
    if count < c:
        end = mid - 1
    else:
        result = mid
        start = mid + 1
print(result)