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가 정답이다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
파이썬 백준 11722 가장 긴 감소하는 부분 수열 (0) | 2021.11.17 |
---|---|
파이썬 백준 11053 가장 긴 증가하는 부분 수열 (0) | 2021.11.16 |
파이썬 백준 13334 철로 (0) | 2021.11.16 |
파이썬 백준 1715 카드 정렬하기 (0) | 2021.11.15 |
파이썬 백준 1655 가운데를 말해요 (0) | 2021.11.15 |