[Baekjoon 2110 / Python / 골드4] 공유기 설치

문제

import sys

input = sys.stdin.readline

# 집, 공유기 개수

N, C = map(int, input().split())

house = [int(input()) for _ in range(N)]  # 집 좌표

house.sort() # 집을 순서대로 정렬

# 이분 탐색으로 인접 공유기 간의 최소 거리를 찾는다

def binarySearch():

    end = house[-1] - house[0] # 최대 거리

    if C == 2:

        return end

    start = 1 # 최소 거리

    result = 0 # 결과를 저장할 변수

    # 최적의 거리를 찾을 때까지 반복한다

    while start < end:

        cur = house[0] # 마지막으로 공유기를 설치한 집 ( 첫번째 집에는 반드시 공유기를 설치해야 함 )

        cnt = 1 # 공유기 설치한 개수

        mid = (start + end) // 2

        for i in range(N):

            if house[i] - cur >= mid: # 마지막 설치 위치부터 어떤 집까지의 거리가 최소 거리 이상이라면

                cur = house[i] # 마지막 설치 위치 갱신

                cnt += 1 # 공유기 설치

        if cnt >= C: # 공유기가 충분히 설치되었다면 결과 갱신 및 최소거리 늘려보기

            result = mid

            start = mid + 1

        elif cnt < C: # 공유기가 전부 설치되지 못했다면 최소거리 줄여보기

            end = mid

   

    return result

print(binarySearch())

 

애를 좀 먹은 문제다.

 

이분탐색은 무엇을 기준으로 이분 탐색을 하느냐를 판단하는 게 정말 중요한 것 같다.

처음엔 입력으로 받는 집(house 리스트)을 기준으로 이분 탐색을 하려 했는데 집 간의 거리가 들쭉날쭉이라 이걸 어떻게 풀지 싶었지만, 최소 거리를 기준으로 이분 탐색을 하면 되는 것이었다.

 

리스트로써 존재하는 데이터여야 이분 탐색이 가능하다고 생각한 나의 착각이었다. 구해야 하는 값은 최소 거리이니 그냥 최소, 최대값만 정해두고 이분 탐색을 실시하면 된다.

 

집 위치가 중복되지 않으니 최소 거리는 1, 최대 거리는 첫 집과 마지막 집 사이의 거리로 한다. 당연히 mid값은 start + end // 2로 한다. 

 

첫 번째 집부터 차례로 방문하며 이전에 공유기를 설치한 집과의 거리가 mid값(최소거리) 이상이면 공유기를 설치하고, 모든 집을 돈 후에(반복문이 끝난 후에) 공유기가 몇 대가 설치되었는지 확인한다. C개 이상으로 설치되었다면 최소 거리를 늘려 공유기 수를 줄이고, C개 미만으로 설치되었다면 최소 거리를 줄여 공유기 수를 늘려본다.

 

설치된 공유기 수가 정확히 C개로 맞아 떨어져도 이분 탐색을 종료하면 안 되고 최적의 거리를 찾기 위해 끝까지 탐색해야 한다. 최소값이 다른 경우에도 공유기 개수가 같을 수 있기 때문이다.