[백준/파이썬/이진탐색] 16주차 문제풀이 #2110 공유기 설치

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

이진탐색!

무엇을 구해야 하는가?
ㄴ두 공유기 사이의 거리의 최대 값 (start, end 범위 설정)
그것을 구해야 하는데 필요한 조건은?
ㄴ공유기의 개수 (target)

import sys

#해당 거리로 공유기를 몇개 세울 수 있는지 계산
def router_cnt(distance):
    cnt=1
    index=home[0]
    for i in range(1,n):
        if distance+index<=home[i]:
            cnt+=1
            index=home[i]
    return cnt
    

def binary_search(target, start, end):
    result=0
    while start <= end:
        mid = (start+end)//2
        cnt=router_cnt(mid)
        if cnt<target:
            end = mid-1
        else:
            result=mid
            start=mid+1
    return result

n,c = map(int,sys.stdin.readline().split())
home = [ int(sys.stdin.readline().rstrip()) for _ in range(n)]

home.sort()
print(binary_search(c, 0, max(home)-min(home)))