[Python] BOJ / 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)가 한 줄에 하나씩 주어진다.

출력

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

풀이

일반적인 탐색 방법을 사용하면 시간초과가 발생하는 문제이다.

 

따라서 이진 탐색 알고리즘을 사용하여 풀이하였다.

 

구현 방식은 다음과 같다.

 

1. 먼저 집의 좌표를 입력받은 뒤, 이진 탐색을 하기 위해 정렬을 수행한다.
2. 왼쪽 포인터(min_dist)를 최소 거리로, 오른쪽 포인터(max_dist)를 최대 거리로 초기화한 후, 이진 탐색을 수행한다.
3. 두 포인터의 합을 2로 나누어 기준이 될 거리(dist)를 구한다.
4. 3번에서 구한 거리(dist)를 기준으로 배열(x)을 탐색하며 두 집의 사이의 거리(x[i] - prev)가 기준 거리(dist)보다 크거나 같을 경우 설치한 공유기의 개수(cnt)를 증가시킨다.
5. 4번의 과정이 끝나고 만약 설치한 공유기의 개수(cnt)가 보유하고 있는 공유기의 개수(c)보다 크거나 같을 경우 간격을 더 크게하거 설치할 수 있는 경우가 있을 수 있다는 것이므로 왼쪽 포인터(min_dist) 값을 증가시켜 공유기 사이의 간격을 증가시킨 다음 다시 이분 탐색을 수행한다. 그렇지 않을 경우 오른쪽 포인터(max_dist) 값을 감소시켜 공유기 사이의 간격을 감소시킨 다음 이분 탐색을 수행한다.
6. 출력값(ans)은 설치한 공유기의 개수(cnt)가 조건을 충족했을 때마다 갱신시켜준다.

---

import sys
input = sys.stdin.readline

def solve():
    ans = 0
    min_dist, max_dist = 1, x[-1] - x[0]

    while min_dist <= max_dist:
        dist = (min_dist + max_dist) // 2
        prev = x[0]
        cnt = 1

        for i in range(1, n):
            if x[i] - prev >= dist:
                cnt += 1
                prev = x[i]

        if cnt >= c:
            min_dist = dist + 1
            ans = dist
        else:
            max_dist = dist - 1

    return ans

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

x.sort()
print(solve())