BOJ-2110 공유기 설치

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

문제 소개

집 N개가 수직선 위에 있을 때, 공유기 C개를 적당히 설치하려고 한다.

N과 C, 그리고 집들의 좌표가 주어졌을 때 가장 인접한 두 공유기 사이의 최대 거리를 구한다.

문제 풀이

매개 변수 탐색 (parametric search) 을 이용하여 풀이하였다.

이진 탐색을 기반으로 풀 것이므로, 집들의 좌표를 리스트 house에 담아 오름차순으로 정렬하였다.

우리가 찾고자 하는 값은 닫힌 구간 [1, house[-1] - house[0]]에 존재한다.

구간이 정해졌으므로 이진 탐색을 진행하며, mid값을 간격으로 하여 공유기를 설치할 수 있는지 여부로 low 또는 high 값을 조정한다.

최대값을 찾는 이진 탐색이므로 공유기를 설치할 수 있는 경우 low = mid + 1이 되는 동시에 결과값인 result를 mid로 업데이트하고, 설치할 수 없는 경우 high = mid - 1이 된다.

mid였던 값들은 모두 해당 간격으로 공유기를 설치할 수 있음이 보장되지만, mid + 1부터는 그렇지 않으므로 low <= high 인 동안 반복하여 탐색한다.

코드

from sys import stdin
input = lambda: stdin.readline().rstrip()

# 특정 간격 값을 찾는다
# 1 ~ (house[-1] - house[0]) 사이에서 간격을 찾아야 함
# 계속 true이다가, 어느 값을 넘어가는 순간 False가 되는데, 그 어느 값을 찾아야 함


# 공유기를 length의 간격으로 설치할 수 있는지 확인하는 함수
def is_available(arr, length):
    cnt = 1
    last = arr[0]
    for i in range(1, n):
        if arr[i] - last >= length:
            cnt += 1
            last = arr[i]

    return cnt >= c


# 매개 변수 탐색 함수
def parametric_search(house):
    low, high = 1, house[-1] - house[0]
    result = 1
    while low <= high:
        mid = (low + high) // 2

        # 공유기 설치가 가능한지 확인
        if is_available(house, mid):
            result = mid
            low = mid + 1
        else:
            high = mid - 1
    return result


n, c = map(int, input().split())
house = [int(input()) for _ in range(n)]
house.sort()

print(parametric_search(house))