공유기 설치

p. 369

 

n, c = map(int, input().split())

house=[]

for i in range(n):
    house.append(int(input()))

house.sort()

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

while start <= end:
    middle = (start+end)//2
    h = house[0]
    count = 1

    for i in range(n):
        if h+middle <= house[i]:
            count += 1
            h = house[i]

    if count >= c:
        result = count
        start = middle + 1
    else:
        end = middle - 1

print(result)

 

 

* 구해야할 것 : 최대 두 공유기 사이의 거리

--> 거리를 조절해가며 최대의 거리를 찾아야 해

      거리를 이진탐색으로 조절해보자

--> 단순 탐색을 할 경우 시간 초과 ( 집의 개수 최대 200,000 ) -> O(N^2)