백준 2110번: 공유기 설치 (Python)

.

접근

이전 단계들에서 풀었던 이분탐색 알고리즘을 이용하여 풀 수 있는 문제고, 동일한 방식으로 탐색하면 된다.

2021.04.05 - [코딩/백준 (Python)] - 백준 1654번: 랜선 자르기 (Python)

백준 1654번: 랜선 자르기 (Python)

공유기 사이의 거리가 될 수 있는 값의 최소값은 1이고, 최대값은 (x[-1] - x[0]) // (c - 1) 이다.

예제 코드에서 주어진 집 좌표 [1, 2, 4, 8, 9] 에서 공유기 사이의 거리가 1일 때, 공유기는 모든 집에 설치될 수 있고, 공유기의 개수는 5이다. 따라서 공유기 사이의 거리를 늘린다. 공유기 사이의 거리가 4일 때, 공유기는 [1, 8] 에만 설치될 수 있고, 공유기의 개수는 2개이다. 따라서 공유기 사이의 거리를 좁힌다. 이러한 알고리즘으로 이진탐색을 구현하여 공유기 개수를 만족하는 공유기 사이의 최대 거리를 구하면 된다.

코드

import sys

n, c = map(int, sys.stdin.readline().split())
x = []
for _ in range(n):
    x.append(int(sys.stdin.readline()))
x.sort()


def router(d):
    cnt = 1
    prev = x[0]
    for i in range(1, len(x)):
        if prev + d <= x[i]:
            prev = x[i]
            cnt += 1
    return cnt


def binarysearch(mind, maxd, target):
    midd = (mind + maxd) // 2
    if mind >= maxd - 1:
        return mind
    if router(midd) < target:
        return binarysearch(mind, midd, target)
    else:
        return binarysearch(midd, maxd, target)


print(binarysearch(1, (x[-1] - x[0]) // (c - 1) + 1, c))

더 생각해 볼 것?

이분탐색 알고리즘은 굉장히 여러가지 문제를 해결할 수 있는 알고리즘이 될 수 있는 것 같다. 이분탐색 알고리즘을 문제에 맞게 적용할 수 있는 숙련도를 갖추어야겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!