[백준] 2110번 - 공유기 설치 (이분 탐색) - 결과 포함

www.acmicpc.net/problem/2110

2110번: 공유기 설치

이 문제는 바로 해결 방법이 떠오르지 않아서 다른 분의 해결 방법을 참고했다.

blog.naver.com/kks227/220444432628

[2110번] 공유기 설치

사실 이전의 파라메트릭 서치 유형의 문제이고 크게 다르지 않은 문제이다.

임의의 거리로 공유기를 배치했을 때 주어진 공유기를 모두 설치할 수 있는 지를 결정하는 문제로 바꾸면 쉽게 해결할 수 있다.

 

일단 가장 왼쪽의 집에는 무조건 공유기를 설치한다.

그 이유는 어떠한 경우에도 가장 왼쪽의 집에 공유기를 설치했을 때 원하는 답이 나오지 않는 경우가 없기 때문이다.

 

가장 왼쪽의 집에 공유기를 설치하지 않고 다른 집들에 설치했을 때도 원하는 답이 나오는 경우가 존재하지만,

이 경우에도 가장 왼쪽의 집에 설치하는 것과 결과는 다르지 않다.

 

이후에 다음 집과의 거리를 비교한다.

집을 하나씩 건너가면서 현재 집과 거리를 비교해 우리가 미리 정의한 범위의 중간값(mid)보다 큰 지 살핀다.

집과의 거리가 mid 보다 크거나 같다면 공유기를 설치하고 설치한 집부터 다시 비교를 시작한다.

만약 거리가 mid 보다 작다면 공유기를 설치하지 않고 집을 건너간다.

 

mid보다 크거나 같은 경우 바로 공유기를 설치하는 이유는 손해볼 이유가 없기 때문이다.

처음에 무조건 공유기를 설치한 것과 같은 이유이다.

만약에 mid보다 크거나 같아도 다음 집으로 넘어갔을 때 정답을 얻을 수도 있지만,

이 경우에도 mid보다 크거나 같았을 때 바로 공유기를 설치해도 정답과 무관한 결과를 얻는다.

 

그렇기 때문에 mid보다 크거나 같은 경우에 바로 공유기를 설치하는 것이 인접한 두 집의 거리를 최대로 하면서 공유기를 모두 설치할 수 있는 확률을 높이는 최적의 방법이다.

import sys

n, c = map(int, sys.stdin.readline().rstrip().split())
data = list()
for i in range(n):
    data.append(int(sys.stdin.readline().rstrip()))

data.sort()

start = 1
end = data[-1] - data[0]


def possible(current, wifi):
    i = current + 1
    while i < n:
        if wifi == 0:
            return True
        if data[i] - data[current] >= mid:
            wifi -= 1
            current = i
            i = current + 1
        else:
            i += 1
    if wifi == 0:
        return True
    return False


while start + 1 < end:
    mid = (start + end) // 2
    if possible(0, c - 1):
        start = mid
    else:
        end = mid

print(start)

위의 블로그 글을 참조해서 대부분 유사한 코드이다.

아직 이분 탐색에 대해서 더 공부해야 할 것 같다.