[PS] BOJ 2110 / 공유기 설치

문제 링크: https://www.acmicpc.net/problem/2110

결정 문제를 잘 정의하면 어렵지 않게 풀 수 있습니다.

풀이

매개변수 탐색

문제의 내용을 요약해보면, $N$개의 집 중에서 최소 $C$개의 공유기를 놓을 수 있도록 하는 인접한 두 공유기 사이의 거리의 최대값을 구하면 됩니다.

구해야 하는 것은 '인접한 두 공유기 사이의 거리의 최댓값' 이므로, 문제를 다르게 생각해봅시다.

인접한 두 공유기 사이의 거리가 $K$ 이상일 때, 주어진 집들에 배치할 수 있는 공유기의 개수가 $C$ 이상인가?

위의 형태로 인접한 공유기 사이의 거리 $K$에 대한 문제를 생각해볼 수 있습니다.

이 결정문제로 매개변수 탐색을 통해 $K$의 최댓값 (upper-bound)를 구할 수 있습니다.

결정 문제의 답을 T/F로 나타내면,
TTTT...TFFFF 꼴이 되며, 가장 오른쪽 끝에 위치하는 T의 위치를 찾는 이분 탐색입니다.

입력 처리

집의 좌표는 정렬되어 주어지지 않습니다. 매개변수 탐색을 위해 정렬해야 합니다.

N, C = map(int, input().split())
houses = sorted(int(input()) for _ in range(N))

매개변수 탐색 구현

매개변수 탐색을 통해, 인접한 두 공유기 사이의 최단 거리 $K$의 최댓값을 찾습니다.

❓매개변수 탐색의 반복문 조건이 left + 1 < right인 이유

$K$의 값으로 사용하는 mid는 (left + right) / 2로 정의됩니다. 만약 left + 1 == right인 상황에서, mid는 언제나 left와 같습니다. 이 경우, 무한 반복에 빠지게 됩니다.
따라서, mid != left인 경우만 탐색하기 위해 left + 1 < right로 조건을 설정했습니다.

❓ right가 (마지막 집) - (처음 집) + 1로 설정된 이유

집 좌표를 정렬했을 때, 처음 집과 마지막 집의 거리 차가 두 공유기 사이 거리의 최댓값이 됩니다. 이를 $D$라고 하면, $1 \leq K \leq D$입니다.

현재 반복문의 조건인 left + 1 < right, right의 경우 탐색 범위에 포함되지 않습니다 (mid == right가 되는 경우가 존재하지 않음)
하지만, $K$는 최대 $D$까지는 될 수 있어야 하기 때문에, $D$는 탐색 범위에 포함되어야 합니다. 따라서 right를 $D + 1$로 설정해 $K$가 온전히 탐색될 수 있도록 했습니다.

# 매개변수 탐색
left = 1
right = houses[N - 1] - houses[0] + 1

while left + 1 < right:
    mid = (left + right) // 2 # 공유기 사이 최소 간격 K

    # 결정 문제 풀이
    cnt = 1 # 첫 번째 집에 공유기 설치
    last_pos = houses[0] # 바로 직전에 공유기를 설치한 위치
    for i in range(1, N):
        if houses[i] - last_pos >= mid:
            cnt += 1
            last_pos = houses[i]
    if cnt >= C: # 결정 문제 T
        left = mid
    else: # 결정 문제 F
        right = mid
        
print(left) # upper-bound를 찾는 매개변수 탐색에서, left값이 탐색 결과가 된다.

전체 코드

input = open(0).readline
N, C = map(int, input().split())
houses = sorted(int(input()) for _ in range(N)) # 집 좌표 정렬하기

# 매개변수 탐색
left = 1
right = houses[N - 1] - houses[0] + 1
while left + 1 < right:
    mid = (left + right) // 2 # 공유기 사이 최소 간격

    # 결정 문제 풀이
    cnt = 1 # 첫 번째 집에 공유기 설치
    last_pos = houses[0] # 바로 직전에 공유기를 설치한 위치
    for i in range(1, N):
        if houses[i] - last_pos >= mid:
            cnt += 1
            last_pos = houses[i]
    if cnt >= C: # 결정 문제 T
        left = mid
    else: # 결정 문제 F
        right = mid
        
print(left) # upper-bound를 찾는 매개변수 탐색에서, left값이 탐색 결과가 된다.