[백준] 2110번 공유기 설치 - 파이썬(Python)

문제 (링크)

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

나의 풀이

import sys
input = sys.stdin.readline

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

arr.sort()

end = arr[-1] - arr[0]
start = 1
ans = 0

while start <= end:
    mid = (start + end) // 2
    count = 1
    current_router = arr[0]
    tmp = float("INF")

    for i in range(1, n):
        if current_router + mid <= arr[i]:
            tmp = min(arr[i] - current_router, tmp)
            count += 1
            current_router = arr[i]

    if count < c: # 공유기 설치를 더 해야함 -> 간격을 짧게 해야 함
        end = mid - 1

    elif count >= c: # 공유기 설치가 완료 or 더 많이 됨 -> 간격 늘려야 함
        start = mid + 1
        ans = max(ans, tmp)
    

print(ans)

풀이법 및 코드 설명

이 문제는 공유기 사이의 거리를 기준으로 이진탐색을 진행해줘야한다.

 

따라서, start와 end를 각각 1과 가장 높은 숫자의 집과 가장 낮은 숫자의 집의 차이로 초기화 해준다. (arr[-1] - arr[0])

 

이후, 이진탐색을 진행하며 특정 공유기와 다른 공유기 간의 간격이 mid 이상인 것을 뽑아준다.

 

두 공유기 사이의 간격이 mid이상이란 것은, mid 이상의 간격을 두고 설치가 가능하다는 뜻이므로, 공유기 설치가 가능하다는 의미로 count에 1을 더해준다.

 

이 때, 중요한 것은 두 공유기 간 실제거리는 mid가 아닌 arr[i]와 current_router를 뺀 값이다.

 

즉, mid가 4일 때, 1과 6, 1과 7 모두 설치가 가능하지만 두 공유기 간 실제 거리는 5와 6이다.

 

따라서 해당 값들 중 가장 작은 값이 가장 인접한 공유기 사이의 거리가 된다.

 

한 번 이진탐색을 할 때마다 해당 값을 뽑고, 이 값의 최대값을 구해주면 문제를 해결할 수 있다.