[백준] 2110 - 공유기 설치(python)

문제 링크

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 해야한다.

예시를 들자면

1,2,4,8,9에 3개의 공유기를 설치하려면 1,4,9 혹은 1,4,8에 위치해야 공유기 사이의 거리를 최대로 할 수 있다.
처음에 바보도 아니고 이 말을 이해를 못했는데...

만약 공유기 사이의 최소 거리를 3이라고 지정했다.
두 공유기 사이의 거리를 가장 최대로 하고 싶다면 1부터 시작해야한다. 공유기는 1개 설치됐다.
2에 설치하게 된다면 공유기 사이의 거리가 1이다. 그래서 안된다.
4에 설치하게 된다면 공유기 사이의 거리가 3이다. 가능하다. 공유기는 2개 설치됐다.
이제 4에서 다음 공유기 사이의 거리를 구해야한다.
8에 설치하게 된다면 공유기 사이의 거리가 4가 된다. 공유기는 3개 설치됐다.
혹은, 9에 설치하게 된다면 공유기 사이의 거리가 5가 된다. 그렇기에 9도 가능하다.
그래서 1,4,9 혹은 1,4,8에 위치가 가능한 것이다.

하지만 공유기 사이의 최소 거리를 5라고 지정했다.
이 또한 가장 최대로 구하고 싶기에 1부터 시작해야한다. 공유기는 1개 설치됐다.
2에 설치하게 된다면 공유기 사이 거리는 1이다. 안된다.
4에 설치하면 거리가 3이다. 안된다.
8에 설치하면 거리가 7이다. 가능하다. 공유기는 2개 설치됐다.
이제 8에서 다음 공유기 사이의 거리를 구해야한다.
9에 설치하게 된다면 8과 9간의 공유기 사이의 거리가 겨우 1이다. 그렇기에 안된다.
공유기가 총 2개가 설치됐기 때문에 최소 거리가 5일 수 없다.

즉, 이 문제는 공유기 간의 최소거리를 최대화 하는 것이 목표다.

조건에서 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000) 라고 써져있어서 이분탐색 그 중에서도 파라매트릭 서치를 사용해야 한다는 것을 캐치했다.

start는 두 사이의 거리가 1인 것이 최소 값이니까 1로 지정
end는 정렬한 좌표값의 가장 큰 값과 작은 값을 뺀 것이 최대 거리이기 때문에 그렇게 지정했다.

그 외는 기본 틀에서 문제 해결 완료!

import sys

input = sys.stdin.readline

n, c = map(int,input().split())
l = []
for i in range(n):
    l.append(int(input()))

l.sort()

start = 1
end = l[-1] - l[0]
answer = 0
while start <= end:
    mid = (start + end) // 2
    total = 1
    tmp = l[0]
    for i in l[1:]:
        if i - tmp >= mid:
            tmp = i
            total += 1
    if total < c:
        end = mid - 1
    else:
        answer = mid
        start = mid + 1

print(answer)