[Python]이분탐색 백준 2110

문제

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

두 공유기 사이의 거리를 기준으로 이분탐색을 시행한다.

두공유기의 거리를 임의로 정하고 집의 좌표를 정렬한후 각 거리만큼 더해가며 집사이

의 거리가 임의의 거리보다 크다면 공유기를 설치해준다.

이렇게 설치를 하고 공유기의 설치수가 원하는 공유기의 개수보다 많거나 같다면 거리를

늘려서 다시 탐색하고 공유기수가 작개 나온다면 거리를 줄여서 다시 계산한다. 

처음 짠 코드가 오래걸려서 입출력을 바꾸었다.

import sys
input=sys.stdin.readline
N,C=map(int,input().split())
c_list=[]
for i in range(N):
    c_list.append(int(input()))
 
c_list.sort()
 
 
min_degree=1
max_degree=c_list[-1]
result=0
while min_degree<=max_degree:
    mid=(max_degree+min_degree)//2
 
    sum_c=1#공유기 갯수 첫지점은 넣고 시작
    tmp=c_list[0]#이전집 저장
    for i in range(1,N):
        if tmp+mid<=c_list[i]:#mid보다 멀리있으면 공유기 설치
            sum_c+=1
            tmp=c_list[i]
            if sum_c>=C:#더많이 설치되었거나 같다면 더이상
                break
 
    if sum_c>=C:#공유기 설치수가 원하는 설치수보다 많거나 같다면 거리를 늘린다.
        min_degree=mid+1
        result=mid
    else:
        max_degree=mid-1
 
print(result)