[백준 2110번] 공유기 설치 문제 풀이 (with Python)

 

< 문제 >

 

 

< 입출력 >

 

 

 

< 풀이 >

이분 탐색을 이용하면 간단하게 풀린다. 거리를 이분 탐색의 변수로 놓는다는 생각이 새로운 문제였다.

공유기는 같은 집에 있을 수 없으므로, start = 1, end = 가장 먼 집의 거리로 놓고, 가운데를 mid로 놓아 mid 거리만큼에 공유기를 설치했을 때 설치되는 공유기의 개수와 C를 비교해서 start나 end의 크기를 바꾸어 주었다.

 

 

 

< 코드 >

import sys
input = sys.stdin.readline

arr = []
N, C = map(int, input().split())
for i in range(N):
    arr.append(int(input()))

arr.sort()

start = 1       # 두 공유기 사이의 거리 최소값
end = arr[-1] - arr[0]   # 두 공유기 사이의 거리 최대값
answer = 0

while start <= end:
    mid = (start + end) //2
    current = arr[0]
    count = 1
    for i in range(1, len(arr)):
        if arr[i] >= current + mid:
            count += 1
            current = arr[i]

    if count >= C:
        start = mid + 1
        answer = mid
    else:
        end = mid - 1
        
print(answer)