[복기] 2110번: 공유기 설치

문제

백준 2210번: 공유기 설치

어려웠던 점

분명 풀었던 문제인데 아무리 문제를 읽어도 솔루션이 떠오르지 않았다. 이분탐색이라는 걸 알고봐도 모르겠다. 이분탐색을 한다는 것은 어떤 값을 탐색하기 위한 것일텐데, 해당 문제에서는 찾을 수 있을만한 값이 없어보였기 때문이다. 그래서 30분만에 포기하고 정답코드를 봤다.

솔루션

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
a = [0] * n
for i in range(n):
    a[i] = int(input())

a.sort()

def bsearch(arr, start, end):
    answer = 0
    while start <= end:
        mid = (start+end)//2
        cur = arr[0]
        count = 1

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

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

    return answer

print(bsearch(a, 0, a[-1]-a[0]))

공유기 설치 문제에서 탐색할 값은 '공유기 사이의 거리'이다. '공유기 사이의 거리'를 탐색하며 설치할 수 있는 공유기 개수를 충족하는지 여부를 체크하고 범위를 바꾸어서 계속 체크한다. 반복문이 끝났을 때, answer에 저장된 값이 정답이다.

복기

솔루션을 보니 예전에 이렇게 풀었었다는게 생각났다. 그때나 지금이나 솔루션을 보고 감탄하긴 마찬가지였다. 어떻게 이런 방식으로 푸는거지. 나도 아직 문제 풀이량이 부족하다. 또 이분탐색 이론 공부도 다시 해야겠다. 아마 '가장 인접한/짧은/가까운 무엇을 최대로 하는 거리/시간'을 구하는 문제는 이분탐색을 요구하는 문제인 것 같다.