[백준 파이썬 2110번 공유기 설치] 이진 탐색의 활용

일단 문제를 보자마자 이진탐색임을 직감은 했지만 이진탐색을 사용하는 방법이 좀 아쉬웠다.

 

아이디어가 좋은 문제인 것이 가장 인접한 두 공유기 사이의 최대 거리를 구하기 위해서는 최대한 일정한 크기로 잘라야 한다는 점이다

그렇기 때문에 어느정도의 사이즈로 잘라야 일정하게 짤리는가를 찾는 문제로 치환될 수 있다.

 

따라서 이진탐색을 공유기를 찾는데 활용하는 것이 아니라 잘려지는 길이를 이진탐색으로 찾는 문제였다

 

구현에서 핵심은 잘려지는 길이를 찾는 것이기 때문에

start와 end를 인덱스로 잡는 것이 아니라 길이로 잡아야 한다

즉, 최소 1 최대는 시작부터 끝까지의 길이로 설정해서 그 사이의 값을 찾도록 구현해야한다

def install_router(seq):
    start = 1
    end = seq[-1] - seq[0]

    while start <= end:
        mid = (start + end) // 2
        current = seq[0]
        count = 1

        for i in range(1, len(seq)):
            if seq[i] >= current + mid:
                count += 1
                current = seq[i]

        if count >= C:
            global answer
            start = mid + 1
            answer = mid
        else:
            end = mid - 1


N, C = map(int, input().split())
routers = []
answer = 0
for _ in range(N):
    routers.append(int(input()))
routers.sort()

install_router(routers)

print(answer)