2021.2.19 [백준] 공유기 설치

이진 탐색 알고리즘

파라메트릭 서치

 

 

Q

 

www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

A

 

이진 탐색 문제이다. 다만, 문제를 그냥 풀기보다는 파라메트릭 서치를 적용하여 결정 문제로 바꾼 뒤에 푸는 것이 훨씬 간단해진다. 가장 인접한 두 공유기 사이의 최대 거리를 구하는 문제이므로, 최대 거리를 범위로 잡고, 공유기를 다 설치할 수 있는지 결정하는 문제로 바꿔서 풀었다.

 

코드

import sys

n, c = map(int, sys.stdin.readline().rstrip().split())

array = list(int(sys.stdin.readline().rstrip()) for _ in range(n))

 

array.sort() #이진 탐색을 위해 오름차순 정렬

 

start = 200000 #min을 제대로 쓰기 위해 큰 값으로 설정
for i in range(n - 1):
    start = min(start, array[i + 1] - array[i]) #집들 사이의 최소 거리
end = array[-1] - array[0] #집들 사이의 최대 거리

while start <= end: 
    mid = (start + end) // 2
    place = array[0] #가장 먼저 있는 집 위치

    count = 1 #공유기 설치 갯수, place에 이미 설치해있다고 본다.
    for i in range(1, n):
        if array[i] >= place + mid: #집 위치 + 거리보다 더 큰 array 값이 있다면 거기에 공유기 설치 가능하므로
            count += 1 #공유기 설치하기
            place = array[i] #집 위치를 이동하기
    if count >= c: #만약 공유기 갯수가 c 이상이라면 최소 거리를 키우기
        start = mid + 1  
    else: #만약 공유기 갯수가 c 미만이라면 최대 거리를 줄이기
        end = mid - 1

print(end) #end와 start 둘 중 어느 것이 정답인지 주의하며 풀기