백준 2110 파이썬(Python) 문제풀이 공유기 설치

문제링크:https://www.acmicpc.net/problem/2110

import sys

N, C = map(int, sys.stdin.readline().split())
home = []
for _ in range(N):
    home.append(int(sys.stdin.readline()))

home.sort()  # 이분 탐색을 위해 정렬
start = 0
end = home[-1]
ans = 0


def binary(arr, s, e):
    while s <= e: # start != end 까지 반복
        m = (s + e) // 2
        current = arr[0]
        count = 1
        for i in range(len(arr)):
            if arr[i] >= current + m: # arr[i]보다 작거나 같으면 count +=1 공유기를 arr[i]에 설치
                count += 1
                current = arr[i]
        if count >= C:  # C를 넘어가면 더 넓게 설치할수있다는 말 => s = m+1
            global ans
            ans = m # 설치 범위 저장
            s = m + 1
        else:  # C를 넘어가지 않는다면 더 좁게 설치해야함으로 e = m - 1 설정하기
            e = m - 1


binary(home, start, end)
print(ans)