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

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

2110번: 공유기 설치

 

공유기 사이의 거리를 mid 값으로 준 후에

산출된 공유기의 갯수에 따라 start 나 end의 값을 증가시키거나 감소시키며 이분탐색한다.

 

목표 공유기 갯수인 c개보다 같거나 많이 설치했을때 가장 인접한 공유기 사이의 거리가 최대가 되도록 하면된다.

 

 

import sys
 
input = sys.stdin.readline
n, c = map(int, input().split())
li = []
for _ in range(n):
    li.append(int(input()))
# 이분탐색을 위한 정렬
li = sorted(li)
 
 
def bi_search(m):
    cnt = 1
    wifi = li[0]
    for i in range(1, n):
        # m 이상 떨어져야함.
        if m <= li[i] - wifi:
            cnt += 1
            wifi = li[i]
    return cnt
 
 
answer = 0
start, end = 1, li[-1] - li[0]
 
while start <= end:
 
    mid = (end + start) // 2
    result = bi_search(mid)
    if result >= c:
        answer = mid
        start = mid + 1
 
    else:
        end = mid - 1
 
print(answer)