백준, 공유기 설치, 2110, 파이썬

[유형]

이분탐색

 

[문제링크]

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

 

[요약]

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

 

[문제풀이]

start = 공유기 간의 거리 최솟값

end = 공유기 간의 거리 최댓값

start와 end의 중간 값인 mid를 구하고, 탐색을 시작한다.

공유기의 갯수가 C보다 크다면, 거리를 넓혀야하므로 mid+1을

공유기의 갯수가 부족하다면, 거리를 좁혀야하므로 mid-1을 해준다.

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()

homes = []
N, C = map(int,input().split())
for _ in range(N):
    homes.append(int(input()))

homes.sort()

start = 1
end = homes[-1] - homes[0]

while start <= end:
    current = homes[0]
    cnt = 1
    mid = (start+end)//2
    for home in homes:
        if home - current >= mid:
            cnt += 1
            current = home

    if cnt >= C:
        start = mid + 1
    else:
        end = mid - 1

print(end)