[백준 2110번 파이썬] 공유기 설치

백준 2110번 링크)

---

---

해결)

최소값을 시작점, 최대값을 처음 집과 마지막 집 사이 거리 (최대거리임) 로 두고 이분탐색을 하였다.
mid=최소값과 최대값의 평균
mid가 설치할 공유기 사이 간격이라 두고,
집과 집사이 거리보다 mid(간격)가 작으면 cnt를 +1 해준다. (공유기 설치)

• cnt 값이 c보다 크면? -> 간격이(mid) 작아 많이 설치 된 것임 => 간격 늘려주기(min=mid+1)
• cnt 값이 c보다 작으면? -> 간격이 너무 큰 상태 => 간격 줄여주기(max=mid-1)
• cnt 랑 c가 같으면? -> 이때의 mid 저장해두고 간격 늘려보자 (min=mid+1)

---

import sys
#sys.stdin=open('input.txt',"r")
input=sys.stdin.readline
n, c = map(int, input().split())
h = [int(input()) for _ in range(n)]
h.sort()
min,max = 1, h[-1] - h[0] #시작점과 총 거리
result = 0
while min <= max:
    mid = (min + max) // 2
    cnt = 1
    in_h = h[0]
    for i in range(1,n):
        if mid <= h[i] - in_h:
            cnt += 1
            in_h = h[i]
    if cnt >= c:
        result = mid
        min = mid + 1
    else:
        max = mid - 1
print(result)