백준 문제 풀이

2110 공유기 설치

import sys


def install_it(lo, hi):
    global N, C, house

    # lo: 정답이 될 수 있는 최소 거리 / hi: 정답이 될 수 있는 최대 거리
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        installed_devices = 1
        previous_house = house[0]

        # mid 이상의 거리만큼 띄어서 공유기를 설치한다.
        for position in house:
            if position >= previous_house + mid:
                previous_house = position
                installed_devices += 1

        # 결정조건: 최소 mid간격으로 설치했을 때 C개 만큼 설치할 수 있는가
        # 조건보다 적게 설치했다. -> 간격을 줄여준다.
        # ~T / F~, upper_bound,  lo 반환
        if installed_devices < C:
            hi = mid
        else:
            lo = mid

    return lo


N, C = map(int, sys.stdin.readline().split())
house = sorted([int(sys.stdin.readline()) for _ in range(N)])

print(install_it(1, house[N-1] - house[0] + 1))

이진 탐색을 공부하면서 ~T / F~에 너무 집중한 나머지 범위 지정의 중요성을 놓쳤다.

이진 탐색중 사용되는 lo, hi값은 정답이 될 수 있는 값이 존재하는 범위에 해당한다.

이 문제를 풀면서 이진 탐색의 결과를 '공유기를 설치할 위치'로 지정했다.

하지만 이렇게 해서는 문제가 풀릴리 없었다.

다른 사람의 풀이를 보고 비로소 이 문제의 답인 가장 가까운 두 공유기 사이의 거리를 mid로 설정했다.
범위는 1 ~ 가장 오른쪽의 집 위치 - 가장 왼쪽의 집 위치로 지정했다.