[Algorithm] 백준 #2110 공유기 설치

 

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

 

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
position = [int(input()) for _ in range(N)]
position.sort()
# 가장 인접한 공유기 사이의 최대 거리 구하기
# 집 사이의 최소/최대 거리
start, end = 1, position[-1] - position[0]
result = 0

while start <= end:
    mid = (start + end) // 2
    cnt = 1  # 설치하는 공유기 갯수
    current = position[0]  # 마지막으로 설치된 공유기의 위치

    for i in range(1, N):
        if current + mid <= position[i]:  # 현재 집에서 다음 집까지의 거리가 mid 이상인 경우 -> 공유기 설치
            cnt += 1
            current = position[i]
    if cnt >= C:  # 지정한 갯수보다 현재 설치된 공유기 갯수가 많다면 -> 설치 간격을 넓힌다
        result = mid
        start = mid + 1
    else:  # 지정한 갯수보다 현재 설치된 공유기 갯수가 적다면 -> 설치 간격을 좁힌다
        end = mid - 1

print(result)

 

 

공유기를 설치할 거리를 이분탐색을 이용하여 결정한다.

이분탐색의 시작과 끝을 집 사이의 최소거리, 최대거리로 설정한다. 

 

예제로 주어진 집의 위치가 [1, 2, 8, 4 ,9]를 보면

start = 1, end = 8로 설정하고 mid = (1+8)//2 = 4 이다.

이 mid 값을 기준으로 공유기 설치 여부를 결정하게 되는데, (현재 집 ~ 다음 집)의 거리가 mid를 초과한다면 공유기를 설치한다. 

 

현재 mid=4이므로, 1과 8에 설치가능하다. 즉, 2개의 공유기만 설치가능하므로, mid의 값을 줄여가며 적당한 거리를 찾아나간다.