[백준] 2110 공유기 설치 (파이썬 python)

 

 

문제 링크

 

 

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

2110번: 공유기 설치

 

 

문제

 

 

 

 

 

문제 풀이

 

 

이진 탐색을 통해 풀이를 했다.

입력받은 집의 위치에 대해 먼저 정렬을 진행하고,

이진 탐색에 대한 끝점을 제일 긴 거리로 처음에 두어 이진탐색을 진행한다.

변수 current는 공유기를 둔 위치를 나타낸다.

 

import sys

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

house.sort()

start = 1
end = house[-1] - house[0]
result = []

while start <= end:
    count = 1
    mid = (start + end) // 2
    current = house[0]
    for x in house:
        if current + mid <= x:
            count += 1
            current = x
    if count >= C:
        start = mid + 1
        result.append(mid)
    else:
        end = mid - 1

print(max(result))