[백준] 2110 : 공유기 설치

공유기 설치

https://www.acmicpc.net/problem/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

5 3
1
2
8
4
9

예제 출력 1 

3

힌트

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

---

코드

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
home = [int(input()) for _ in range(n)]
home.sort()

# 공유기 사이의 가능한 최소거리, 최대거리
start, end = 1, home[-1] - home[0]

while start <= end:
    mid = (start + end) // 2
    mach = 1 # 공유기 개수, 1번째 자리에는 무조건 설치
    tmp = home[0] # 공유기 설치 시작 위치
    for i in range(1, n):
        if home[i] - tmp >= mid:
            mach += 1
            tmp = home[i]
    if mach >= c:
        res = mid
        start = mid + 1
    else:
        end = mid - 1

print(res)

풀이

우선 해당 문제를 어떻게 접근해야 할 지 상당히 어려웠다. 이분탐색을 이용해야 한다는 것은 금방 캐치하였지만, start, end 값을 무엇으로 지정해주어야 할 지 어려움을 겪었다. 

우선 이분탐색을 사용하기 위해서는 리스트가 정렬되어 있어야 하기 때문에 sort() 함수를 이용하여 정렬해준다. start는 공유기 사이의 가능한 최소거리, 즉 1을 할당해주고 end는 첫 번째 집과 마지막 집 사이의 거리를 할당해주면 된다.

이제 mid를 start, end의 중앙값으로 하여 1번째 집에 공유기를 무조건 설치하고 mid 거리 간격으로 공유기를 설치해주었을 때 설치하려고 하는 공유기 개수 C개를 만족하는지 확인해본 후, start, end 값을 옮겨주어야 한다.

 

예제 입력을 통해 살펴보자. 5개의 집의 좌표 [1, 2, 4, 8, 9]가 주어지고 3개의 공유기를 설치해야 한다.

1번째 반복

우선 start = 1, end = (9-1) = 8, mid = 4이며, (2번째 집의 좌표)는 2인데 이는 (1번째 집 좌표 + mid), 즉 1+4보다 그 값이 작으므로 2번째 집에는 공유기를 설치할 수 없다.(3번째 집의 좌표) 또한 4이므로 공유기를 설치할 수 없지만, (4번째 집의 좌표)인 8는 (1번째 집의 좌표 + mid), 즉 1+4보다 그 값이 크므로 4번째 집에는 공유기를 설치할 수 있다. 이제 4번째 집의 좌표가 기준이 되는 집의 좌표가 될 것이다. 이제 (5번째 집의 좌표)는 9인데 이는 (4번째 집의 좌표 + mid), 8+4보다 그 값이 작으므로 5번째 집에는 공유기를 설치할 수 없다. 결과적으로 설치할 수 있는 공유기의 개수는 단 2개 뿐이므로 주어진 조건인 C = 3을 만족하지 못하므로 더 작은 간격으로 공유기를 설치해주어야 하기 때문에 end = mid - 1으로 할당해준다.

2번째 반복

...

 

이러한 반복을 거쳐가면서 가장 인접한 두 공유기 사이의 거리인 res를 출력해주면 된다.