백준 2110 : 공유기 설치 with 파이썬

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

2110번: 공유기 설치

# 포인트

1. 그리디 : 최소구간이 최대가 되기 위해서는 공유기의 간격이 최대로 벌어져야 하므로 항상 첫번째 집에는 공유기가 설치되야 한다

 

2. 집의 좌표가 (0 ≤ x ≤ 1,000,000,000)이므로, 시간복잡도를 줄여주는 이분탐색을 사용

ⓐ탐색범위 : 최소거리(mid)

ⓑ타겟 비교 : 설치할 공유기의 수(c)와 최소거리(mid)를 통해 설치한 공유기의 수(cnt)를 비교

n,c=map(int, input().split())
homes=[int(input()) for _ in range(n)]
homes.sort()
result=0
st, end=1, homes[-1]-homes[0]
while st <= end:
    mid=(st+end)//2

	# mid를 최소값으로 가정한뒤, mid가 최소값을 되는 곳에 공유기 설치(+=cnt)
    cnt=1
    crt=homes[0]
    for i in range(1, n):
        if mid <= homes[i]-crt:
            cnt+=1
            crt=homes[i]
    
    # 공유기 설치한 수(cnt)와 설치해야하는 수(c)를 비교하여 최소값인 mid 갱신
    
    if cnt >=c:				# 설치한 공유기 수가 더 많은 경우, 
        st=mid+1            # 최소길이인 mid를 늘려 간격 늘리면서 공유기 설치를 줄이기			 
        result=mid			# mid의 최대값을 구해야 하기 때문에
    else : 
        end=mid-1
        
print(result)