공유기 설치

• 파라메트릭 서치로 푸는 문제.
• C개로 X 이상의 거리를 유지할수 있다.
• X를 입력으로 받아서, C개의 공유기를 사용해서 공유기 사이의 거리가 전부 X 이상인 배치가 가능한지를 확인하는 함수를 만들면 된다. 이 함수가 true를 리턴하는 X의 최댓값을 이진 탐색으로 찾는다.
• C개의 공유기로 이러한 배치가 가능한지를 확인하는 것은, 그리디한 방법을 적용한다. C개보다 많은 공유기로 간격 유지가 가능하다면, 거기서 공유기를 빼더라도 최소 간격이 좁아지지는 않으니까 뺄수록 C개로도 거리 유지가 가능하다. 따라서 최소 간격을 유지하는 선에서 공유기를 최대한 많이 배치하도록 시도해보고, 그 갯수가 C개 이상이 되면, C개로 배치가 가능하다고 판단할 수 있다. 좌표를 왼쪽에서부터 훑으면서 이전 공유기의 위치와의 간격이 최소간격 이상이 될때마다 공유기를 배치하는 식으로 하면 된다.
• 탐색 범위의 상한은 간단히 잡으면, 처음 집과 마지막 집 사이의 거리로 잡을 수 있다. 좀더 타이트하게 잡는다면, 모든 공유기 간격이 동일하게 배치되었을때의 거리, 즉 {처음집과 마지막집 사이의 거리}/(C-1) 로 잡을 수 있다.
• 먼저 집의 좌표를 정렬해야 하기 때문에 O(NlogN)이 필요하다. 좌표를 정렬시키고 나면, 배치가 가능한지 확인하는 함수는 O(N)에 동작하고, 정답의 후보를 범위 안에서 이진 검색으로 찾아야 하므로, 저 함수를 O(logX)번 호출해야 한다, 따라서 총 시간복잡도는 O(NlogN + NlogX)
• teflib.algorithm.binary_search 함수는 범위내의 최댓값이 아닌 최솟값만 찾아주도록 구현되어 있기 때문에 살짝 바꿔쓸 필요가 있다. 함수를 배치가 불가능한지를 확인하도록 바꿔 만들어서, 배치가 불가능한 최솟값 X를 찾도록 해야 한다. 이렇게 하면 X-1이 배치가 가능한 최댓값이 된다.

"""Solution code for "BOJ 2110. 공유기 설치".

- Problem link: https://www.acmicpc.net/problem/2110
- Solution link: http://www.teferi.net/ps/problems/boj/2110
"""

import sys
from teflib import algorithm


def main():
    def is_impossible(dist):
        count = 1
        prev_pos = x[0]
        for pos in x:
            if pos - prev_pos < dist:
                continue
            prev_pos = pos
            count += 1
            if count >= C:
                return False
        return True

    N, C = [int(x) for x in sys.stdin.readline().split()]
    x = [int(sys.stdin.readline()) for _ in range(N)]

    x.sort()
    upper_bound = (x[-1] - x[0]) // (C - 1) + 2
    print(algorithm.binary_search(1, upper_bound, is_impossible) - 1)


if __name__ == '__main__':
    main()

• Dependency: teflib.algorithm.binary_search