(파이썬) 백준 2110번 "공유기 설치"

---

# 답

import sys

input = sys.stdin.readline
N, C = map(int, input().split())
home = [int(input()) for _ in range(N)]
home.sort()

lo = 1
hi = home[-1] - home[0]
mi = (lo + hi) // 2

while lo <= hi:
    pre = home[0]
    cnt = 1
    for i in home:
        if i >= pre + mi:
            pre = i
            cnt += 1
    if cnt >= C:
        lo = mi + 1
    else:
        hi = mi - 1
    mi = (lo + hi) // 2

print(mi)

 

 

 

 

---

# 풀이 과정

 

이분 탐색을 이용해 풉니다.

 

1) 이 문제에서 요구하는 답은 '공유기 사이의 최단거리의 최댓값'입니다. 즉 '공유기 사이의 거리'를 구해야합니다. '공유기 사이의 거리'는 최소 1 이상일 것이며, 최대 home[-1] - home[0] 이하일 것입니다.

lo = 1
hi = home[-1] - home[0]

 

2) 1부터 home[-1] - home[0] 사이에 있는 수 중에서 중앙값을 골라 mi라고 합시다.

mi = (lo + hi) // 2

 

3) 첫 번째 집부터 거리가 mi 이상 떨어진 집을 앞에서부터 차례대로 골라 공유기를 설치합니다.

pre = home[0]
cnt = 1
for i in home:
    if i >= pre + mi:
    pre = i
    cnt += 1

 

4) 그렇게 해서 설치한 공유기 개수 cnt가 C보다 크거나 같다면, 공유기 거리 mi를 더 늘려도 괜찮다는 뜻입니다. 반대로 cnt가 C보다 작다면 공유기 거리 mi를 더 줄임으로써 보다 많은 공유기가 설치될 수 있도록 해주어야 합니다.

공유기 거리를 조정한 후 2 ~ 4 단계를 반복하여 적절한 공유기 거리 mi를 찾아나갑니다.

if cnt >= C:
    lo = mi + 1
else:
    hi = mi - 1
mi = (lo + hi) // 2