백준 2110번: 공유기 설치 [Python]

작성일 | In
골드 IV 골드 IV

문제

공유기 설치

풀이

공유기 사이의 거리를 적어도 $d$ 이상이 되게끔 $C$개를 설치할 수 있는지 판단해 봅시다.

이때 공유기를 최대한 많이 설치하는 전략은 0번에 하나를 두고 거리가 $d$ 이상이 되는 지점마다 공유기를 설치하는 것입니다.

따라서 $O(N)$에 판단할 수 있고, 이분 탐색을 통해 $O(N\log (\max(x_i) - \min(x_i)))$의 시간 복잡도로 해결할 수 있습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def main():
    N, C = map(int, input().split())
    x = sorted([int(input()) for _ in range(N)])

    def possible(min_dist: int) -> bool:
        cnt = 1
        last = 0

        for i in range(1, N):
            if x[i] - x[last] < min_dist:
                continue
            last = i
            cnt += 1

        return cnt >= C

    lo = 0
    hi = x[-1] - x[0] + 1
    while lo < hi:
        mid = (lo + hi) // 2

        if possible(mid):
            lo = mid + 1
        else:
            hi = mid

    print(lo - 1)


main()

백준 2110번: 공유기 설치 [Python]