마구간 정하기(결정알고리즘)

마구간 정하기(결정알고리즘)

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

 

▣ 입력 설명

첫 줄에 자연수 N(3<=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

 

---

코드

def Count(len):
    cnt = 1 # 말한마리
    endpoint = line[0] # 첫번째 마구간에 첫번째 말 배치
    for i in range(1, n):
        if line[i] - endpoint >= len: # 다음번째 말과 그 전번째 말과의 거리가 len보다 길다면
            cnt += 1
            endpoint = line[i] # 다음번째 말이 endpoint로 설정한다.
    return cnt # 배치한 말의 마릿수를 return

n, c = map(int, input().split()) # 마굿간 좌표, C마리
line = []

for _ in range(n):
    tmp = int(input())
    line.append(tmp)
line.sort() # 좌표 정렬

lt = 1 # 말은 가장 처음과
rt = line[n-1] # 가장 마지막에 디폴트로 놓는다.

while lt <= rt:
    mid = (lt+rt)//2 # mid = 가장 가까운 두 말의 최대 거리
    if Count(mid) >= c: # 놓을 수 있는 말판의 개수가 c보다 크다면
        res = mid
        lt = mid + 1 # 작은 쪽을 없에준다.
    else: # 인접한 말의 거리가 너무 길 때
        rt = mid - 1

print(res)