[Python] 공유기 설치

문제

2110번: 공유기 설치

입력 예시

5 3
1
2
8
4
9

출력 예시

3

문제 풀이

• 공유기를 설치하려는 집들을 오름차순으로 정렬
• 이진탐색을 진행하면서 거리조절
  • 가능한 최소거리와 최대거리를 구해 중간 값을 구한 뒤 그 거리만큼 떨어진 집들에 공유기를 설치했을 때 c개이상인지 확인
  • c개 이상이거나 같다면 값을 저장한 후 최댓값 찾기 위해 오른쪽탐색 
  • c개 미만이라면 왼쪽 탐색
• 저장된 값 출력

코드

import sys
n, c = map(int,sys.stdin.readline().split())
array = []
for _ in range(n):
    array.append(int(sys.stdin.readline()))
array.sort()

start = 1 # 최소 거리차
end = array[-1] - array[0]
result = 0
# 거리 줄여가면서 탐색
while start <= end:
    count = 1 # 공유기 개수
    set_up = array[0]
    mid = (start + end) // 2
    # mid 만큼 증가시켜가면서 공유기 설치
    for i in range(1, n):
        if array[i] >= mid + set_up:
            count += 1
            set_up = array[i]
    # 공유기 수가 같거나 더 많은 경우 범위 넓히기
    if count >= c:
        start = mid + 1
        result = mid
    else:
        end = mid - 1
print(result)