백준 2110 | 이진탐색 | 공유기 설치 [파이썬 python]

2110번: 공유기 설치

 

binary search 카테고리에 들어있는 문제인데 대체 무엇을 이진 탐색해야 하는지 파악하는데 꽤 오랜 시간이 걸렸다.

문제를 읽어보면 '가장 인접한 두 공유기 사이의 거리를 최대로 하는'이라는 문구를 볼 수 있다.

여기서 두 공유기 사이의 거리에 대해 이진 탐색을 수행 해야함을 알 수 있다.

 

코드

import sys
input = sys.stdin.readline

n, c = map(int, input().split()) # 집 N개, 공유기 C개
houses = [int(input()) for _ in range(n)] # 집의 좌표

houses.sort() # 이진 탐색을 수행할 배열 정렬

# 두 공유기 사이의 거리에 대한 이진 탐색
start, end = 1, houses[-1] - houses[0] # 최소=1, 최대=1번집~마지막집
max_len = 0

while start <= end:
    mid = (start + end) // 2 # 두 집 간 거리
    now = houses[0] # 현재 집 위치
    count = 1 # now에 공유기 한 개 설치

    # 현재집위치+거리보다 더 멀리 있는 집이면 공유기를 설치하고 해당 위치를 현재 집으로 변경
    for i in range(n):
        if houses[i] >= now + mid: 
            count += 1
            now = houses[i]
    
    if count >= c:
        max_len = max(max_len, mid) # 두 공유기 사이의 최대 거리 저장
        start = mid + 1
    else:
        end = mid -1

print(max_len)

이진 탐색 범위는 두 공유기 사이의 최소 거리(=1)부터 최대 거리이다.

1번 집에는 무조건 공유기를 설치한다 가정하고(count=1부터 시작), 이진 탐색을 시작한다.

현재 집 위치에서 mid 거리보다 더 먼 거리에 있는 집에는 공유기를 설치할 수 있다.

 

편의상 houses=[1, 2, 4, 8, 9] 각 요소를 집 번호라고 하자.

now=1번 집이고 mid=(1+9) // 2 = 4일 때,

2번, 4번 집은 now+mid보다 작으므로 공유기를 설치할 수 없고, 8번, 9번 집에 설치할 수 있다.

 

코드 자체는 일반적인 binary search 코드와 크게 차이점이 없으나, 이진 탐색의 대상이 무엇인지 떠올리기까지가 어려운 문제였다.