[백준2110번] 공유기 설치 / Python3

문제

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

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

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

입력

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

출력

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

예제 입력 1

5 3
1
2
8
4
9

예제 출력 1

3

나의 풀이

앞서 풀어본 2805번 나무 자르기 문제, 1654번 랜선 자르기 문제와 비슷하였다. 여기서는 공유기들 사이의 거리 중 최대 거리를 찾아내고 그 거리를 이분 탐색하면서 mid값만큼 떨어지면 공유기를 설치하는 과정을 거치면서 설치될 수 있는 개수를 세어 입력 받는 c값과 비교를 하면 서 최댓값을 구하면 되었다.

예제를 가지고 설명을 하면 공유기들 사이의 최대 거리는 9 - 1로 8 이다. 이 8을 가지고 이분탐색을 진행하면 처음에 mid값은 4 이다. 그리고나서 우선 맨 첫 집에 공유기를 설치하고 정렬된 다음 집들을 확인한다. 1과 2는 차이가 1로 mid값인 4보다 작으므로 공유기를 설치하지 않고 넘어간다. 이후 1과 4도 차이가 3으로 넘어가고, 1과 8의 차이가 7이므로 공유기를 설치하면서 기준을 처음 집에서 x가 8인 집으로 변경한다. 이후 9를 확인하면 9와 8 차이가 1이므로 공유기를 설치하지 않는다. 이렇게하고나면 총 공유기가 설치된 집은 x가 1인 집과 x가 8인 집 총 2곳으로 c로 주어지는 3보다 작으므로 다시 start = 1, end = 3으로 이분탐색을 진행하게된다. 이렇게 진행을 하다보면 공유기가 c보다 설치가 많이 될 경우도 있을 것이다. 그러면 더욱 큰 간격으로 설치가 가능하다는 이야기이므로 이분한 곳에서 오른쪽을 탐색하고 그렇지 않다면 왼쪽을 탐색하면 될 것이다.

코드

# 2110번 공유기 설치

# 이진 탐색
def binSearch(start,end,c):
    while start <= end:
        mid = (start + end) // 2

        cnt = 1
        latest = houses[0]  # 최근 공유가 설치된 집
        for i in range(len(houses)):
              # 최근에 공유기가 설치된 집과 현재 집 좌표의 차이
            if (houses[i] - latest) >= mid:
                cnt += 1
                latest = houses[i] # 공유기를 설치하면 최근 집을 최신화

        if cnt >= c:
            p_len.append(mid)
            start = mid + 1
        else:
            end = mid - 1

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

houses = []
for _ in range(n):
    houses.append(int(input()))

# 집을 순서대로 정렬
houses.sort()

p_len = []
binSearch(1,houses[-1] - houses[0],c)

print(max(p_len))