문제

백준 2210 공유기 설치

분류

이분 탐색

코드

N, C = map(int, input().split())
houses = [int(input()) for _ in range(N)]
houses.sort()
max_dist = houses[-1] - houses[0]

start, end = 1, max_dist
answer = 0

def router_counter(dist):
    count = 1
    cur_position = houses[0]
    for i in range(1, N):
        if cur_position + dist <= houses[i]: #이전 집에서 해당 거리보다 멀리 떨어진 집이라면
            count += 1
            cur_position = houses[i]

    return count


while start <= end:
    mid = (start + end) // 2

    if router_counter(mid) >= C:
        answer = mid
        start = mid + 1

    else:
        end = mid - 1

print(answer)

해설

크게 보면, 설치하는 거리를 최소1, 최대 마지막 집 - 첫 번째 집으로 두고, 이 설치거리를 이분 탐색으로 찾는 것이다. 만약 router_counter()라는 함수에서 count가 필요한 설치 개수인 N보다 더 많이 나오면 거리를 늘리는 방식이다.

router_counter에서 if cur_position + dist <= houses[i]는 이전 집에서 해당 거리보다 멀리 떨어진 집이라면 그 집에 설치하고, 이전 집을 갱신한다.