[🥈1 / 백준 2110 / 파이썬] 공유기 설치

 

2110번: 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

예제 입력  5 3 1 2 8 4 9

예제 출력  3

 

힌트

공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.

 

 

풀이

 

이상하게 그리 어려운 난이도가 아닌데도 해석에 애를 먹었던 문제이다.

이분 탐색을 사용하는 목적을 찾지 못했기 때문인 것 같다.

고군분투 끝에 이해한 것은 공유기를 설치할 거리를 이분 탐색으로 결정한다는 것이다.

 

중요한 것은 집들이 수직선상에 위치하고 있다는 것을 생각해야 한다는 점이다.

 

 

예제와 같이 집들이 수직선상에 있다.

 

여기서 이분 탐색을 수행하는데, 1 2 4 8 9 목록의 중앙값인 4가 mid가 되는 것이 아니라

집들 사이의 최소 거리와 최대 거리의 중앙인 (1+8)/2 = 4 (몫만 이용) 가 되는 것이다.

 

마찬가지로 1 2 3 4 10 이라면 mid값은 3이 아닌 (1+9)/2 = 5가 된다.

그리고 이 값을 기준으로 현재 집에서 다음 집의 거리가 mid를 초과한다면 공유기를 설치할 수 있게 된다.

 

예제에서는 mid가 4이기 때문에 1 다음의 집인 2까지의 거리는 1로, 공유기를 설치할 수 없다.

그 다음의 집은 4인데, 마찬가지로 1 까지의 거리가 3밖에 안되기 때문에 공유기를 설치할 수 없다.

다음인 8까지의 거리는 7로, 4 이상이니 드디어 공유기를 설치할 수 있다!

하지만 그 다음인 9는 8까지의 거리가 1이기 때문에 공유기를 설치할 수 없다.

 

정리하자면 공유기 설치 간격을 4 라고 할 때, 총 설치할 수 있는 공유기의 개수는 2개이다.

이는 C = 3이라는 예제 조건을 충족하지 못한다. 따라서 공유기의 간격을 좁히면 된다.

 

만약 간격을 좁힌 뒤 실행한 결과 공유기의 개수가 C를 초과한다면 간격을 다시 넓히면 된다.

위 과정을 이분탐색으로 실행하는 것이다.

 

import math,sys
input = sys.stdin.readline

n,c = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort()
start,end = 1, h[n-1] - h[0]
# 집 사이의 최소 거리, 최대 거리
result = 0

if c == 2:
    print(h[n-1] - h[0])
    # 집이 2개라면 무조건 처음, 마지막 집 사이의 거리
else:
    while(start < end):
        mid = (start + end)//2

        count = 1
        ts = h[0]
        # 마지막으로 설치된 공유기의 위치
        for i in range(n):
            if h[i] - ts >= mid:
                count+=1
                ts = h[i]
        if count >= c:
            result = mid
            start = mid + 1
        elif count < c:
            end = mid
    print(result)