b_공유기설치_2110

문제

집 N개
집 같은 좌표 ㄴㄴ
공유기 C개 설치하려고함
최대한 많은곳에서 와이파이 사용하려고함
가장인접한 공유기 사이의 거리를 가장크게하려고함

답

dp라고생각했다. 응아니얌
어디에 공유기 둘것인지 지정하지말고
공유기 사이를 거리를 지정해야한다

start = 1 # 공유기 거리 최소
end = arr[-1] - arr[0] # 공유기 거리 최대
result = 0

# <span id="재귀로-적절한-두-공유기-사이의-거리를-찾는다"></span>재귀로 적절한 두 공유기 사이의 거리를 찾는다
while (start <= end):
    mid = (start + end) // 2 # 현재 공유기 거리
    current = arr[0]
    count = 1

    # 공유기 설치 몇 대 할 수 있는지 체크
    for i in range(1, len(arr)):
        if arr[i] >= current + mid:
            count += 1
            current = arr[i]
    # 공유기 설치 수가 목표 보다 크면 공유기 사이 거리 늘림
    if count >= C:
        start = mid + 1
        result = mid
    # 공유기 설치 수가 목표 보다 작으면 공유기 사이 거리 줄임
    else:
        end = mid - 1

print(result)