Week 01 ~ 04 : 알고리즘 문제 풀이

파이썬 백준 11053 공유기 설치

정글러 2021. 11. 16. 17:32
import sys
input = sys.stdin.readline

n, c = map(int, input().split())
l = []
for i in range(n) :
    l.append(int(input()))
l.sort()

def Bsearch(list) :
    drangel = 1
    dranger = list[-1] - list[0]
    while drangel <= dranger :
        d = (drangel + dranger) // 2
        now = list[0]
        count = 1
        for i in range(1, n) :
            if list[i] - now >= d :
                now = list[i]
                count = count + 1
        if count >= c :
            maxd = d
            drangel = d + 1
        else :
            dranger = d - 1
    return maxd

print(Bsearch(l))

집들의 위치를 리스트에 받아서 정렬했을 때, 정답 d는 양 끝 두 집의 거리보다 클 수 없다.

1 <= d <= l[-1] - l[0] 라는 정답의 range가 정해졌으니, d를 range의 중간값에 두어 일단 계산해본다.

c개의 공유기를 설치할 수 없다면, range를 아래쪽 절반으로 낮춰야 c개를 설치할 수 있을 것이다.

c개 이상을 설치할 수 있다면, range의 위쪽 절반으로 높여도 c개를 설치할 수 있을 것이다.

c개 이상을 설치 가능한 경우에는 그때의 d를 maxd로 기록한다.

좁혀진 range의 중간값으로 다시 공유기를 설치해보고 c와 비교해가며 range를 좁혀간다.

이를 반복해서 range가 0이 되었을 때, 그때까지 기록된 최대의 최소거리인 maxd가 정답이다.