[백준] 2110번 공유기 설치(python)

1. 문제

https://www.acmicpc.net/problem/2110

2. 풀이

초기 값이 든 배열을 정렬하여 간격을 파악할 수 있게 한 후 이분 탐색을 진행하며 간격의 최대값을 구한다.
반복문 안에서 이전 배열이 들어가야하니 초기 값을 미리 설정해 준 후 비교한 후 초기화하는 것을 반복한다.
이전 값 + 간격이 그 다음값 보다 작거나 같다면 공유기를 설치 가능한 반경이기에 추가한다.

3. 코드

import sys

n,c = map(int,sys.stdin.readline().split())
arr = []

for i in range(n):
    arr.append(int(sys.stdin.readline()))
arr.sort()

start = 1
end = arr[-1] - arr[0]
ans = 0

while start <= end:
    mid = (start + end) // 2
    temp = arr[0]
    cnt = 1

    for i in range(1, len(arr)):
        if arr[i] >= temp + mid:
            cnt += 1
            temp = arr[i]

    if cnt >= c:
        start = mid + 1
        ans = mid
    else:
        end = mid - 1
print(ans)