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

 

 

 

# 이진탐색
# 가장 인접한 두 공유기 사이의 거리를 최대로 하는
# 공유기의 거리를 이진탐색으로 찾는다.
# 설정한 공유기의 거리를 통해 공유기를 몇대 설치할 수 있는지 확인

import sys
n, c = map(int, input().split())
x = sorted(int(sys.stdin.readline()) for _ in range(n)) # 이진탐색을 위해 오름차순 정렬
start = 1 # 시작지점
end = x[-1] - x[0] # 최대 거리
result = 0 # 결과값

while start <= end:
    mid = (start + end) // 2 # 거리
    count = 1 # 공유기 수
    current = x[0] # 현재 위치

    for i in range(1, len(x)):
        if x[i] >= current + mid: # 다음 좌표가 현재 좌표 + 중간값과 같거나 크다면 = 공유기 거리의 최대값 + 위치보다 크다면
            count += 1 # 공유기 설치
            current = x[i] # 현재 좌표를 재설정

    if count >= c: # 설치한 공유기 수가 설치해야하는것보다 같거나 크다면
        start = mid + 1 # 설치 거리를 더 늘림
        result = mid # 결과값 갱신
    else: # 설치한 공유기 수가 설치해야하는 것보다 적다면
        end = mid - 1 # 설치 거리를 더 좁힘 

print(result)

 

 

 

 

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

2110번: 공유기 설치