[이진 탐색 알고리즘] 공유기 설치 S1

기출 : BOJ #2110

 

변경할 값은 인접 공유기 사이의 최대 거리이고 체크할 함수는 해당 거리일 경우 설치 가능한 공유기의 개수를 출력한다

 

공유기 개수가 목표한 값보다 큰경우 답을 갱신하고 범위를 줄여 다시 탐색한다

 

answer = 0
n,c = map(int,input().split())
h = list()
for _ in range(n):
    h.append(int(input()))


h.sort()

def check(val):
    global h
    res = 1
    ex = h[0]
    for p in h:
        if p>=ex+val:
            res += 1
            ex = p
    return res

def bs(st, en, target):
    global answer
    if st>en:
        return -1
    mid = (st+en)//2
    val = check(mid)
    if val>=target:
        answer = mid
        bs(mid+1, en, target)
    else:
        bs(st, mid-1, target)


bs(0,h[n-1],c)
print(answer)