[백준] 백준 python 2110번 문제 및 소스코드

1. 문제 링크

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

 

2. 문제

 

3. 소스코드 및 설명

import sys
input = sys.stdin.readline  #시간 초과 방지

# n: 집의 개수, c: 설치할 공유기 개수
n, c = map(int, input().split()) #입력받은 값을 공백으로 분리

#집의 위치를 리스트에 저장하고 정렬
houses = [int(input()) for i in range(n)]
houses.sort()


#start: 최소 간격(1), end: 최대 간격(집들 간의 최대 거리)
start = 1
end = houses[-1] - houses[0]

#이진 탐색을 통해 공유기를 설치할 수 있는 최대 간격을 찾는 함수
def binarySearch(houses, start, end):
    while start <= end:
        mid = (start + end) // 2 #중간값(현재 탐색하는 간격)
        current = houses[0] #첫 번째 집에 공유기 설치
        cnt = 1 #설치한 공유기 개수(첫 번째 집에 설치했기 때문에 1)
        for i in range(1, n):
            if houses[i] >= current + mid:
                cnt += 1
                current = houses[i]
        #설치한 공유기 개수가 c 이상이면 간격을 더 늘려도 되므로 최소 간격인 start 값을 증가시킴
        if cnt >= c:
            start = mid + 1
            result = mid #가능한 최대 간격을 저장
        else:
            end = mid - 1 #설치한 공유기 개수가 부족하면 간격을 줄인다
    return result #최종적으로 찾은 최대 간격 반환

#최적의 최대 간격 출력
print(binarySearch(houses, start, end))