1. 문제 설명

공유기 설치

2. 문제 분석

집 위치가 담긴 배열이 주어진다. 특정 간격으로 공유기를 설치할 때, 설치 가능한 공유기 간격 중 가장 큰 값을 구한다.

• 공유기를 설치하는 간격이 비교하는 집들 사이의 거리 이하일 때 공유기를 설치할 수 있다. 이때 공유기 '한 대'를 설치했기 때문에 비교하는 기준이 되는 집을 다시 바꾸는 것에 주의하자.

• mid로 구하는 공유기의 간격을, cnt로 이 간격으로 주어진 집들 사이에 공유기를 설치할 때 드는 공유기의 총 개수를 파악하자. cnt가 c 이상이면 이 간격을 쓸 수 있다는 말이다.

3. 나의 풀이

n, c = map(int, input().split())

x = []

for _ in range(n):
    x.append(int(input()))

x.sort()
# 집 위치대로 정렬

start, end = 1, x[-1]-x[0]
# 가장 작은 간격 1부터 가장 긴 간격 (가장 멀리 있는 집 사이 간 거리) 범위
lengths = []

while start <= end:

    mid = (start + end) // 2
    # mid는 공유기 사이의 거리
    cnt = 1
    # 사용할 공유기의 개수 cnt
    cur = x[0]

    for house in x[1:]:
        distance = house - cur
        # 비교하려는 집과 현재 기준 집 사이의 거리
        if distance >= mid:
            # 집들 간의 거리가 공유기 간격보다 크다면 카운트
            cur = house
            # 새로운 공유기를 사용해야 하므로 집 기준점을 다시 변경.
            cnt += 1
            
    if cnt >= c:
        # 사용한 공유기 개수가 c보다 클 때 이 mid를 간격으로 사용할 수 있다.
        lengths.append(mid)
        start = mid + 1
    else:
        end = mid - 1

print(max(lengths))
# 공유기 간격 중 가장 큰 값을 리턴한다.