[백준] 2110번 공유기 설치 (Python 파이썬)

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

2110번: 공유기 설치

문제에서 주어진 대로, N개의 집에 C개의 공유기를 설치한다.

이 때, 가장 인접한 두 공유기 사이의 거리가 최대 가 되도록 해야 한다.

 

즉, 집의 좌표가 [ 1, 2, 4, 8, 9 ] 이고 공유기를 3개 설치 할 때, 공유기를 1, 4, 8 혹은 1, 4, 9 에 설치를 해야

가장 인접한 두 공유기 사이의 거리(1, 4)가 3이 되고, 이 3 보다 작게 설치를 할 수는 없다.

 

그렇다면, 공유기를 설치해야 될 집은 어떻게 찾아야 할까?

가장 간단한 방법으로는 순차 탐색으로 앞에서 부터 일일이 설치 집을 탐색해보며 실행하는 방법이 있지만,

가장 비효율적인 방법이며 분명 시간 제한 오류가 난다.

이러한 탐색 문제를 가장 빠르게 푸는 방법은 바로 이진 탐색(Binary Search) 이다.

---

이진 탐색을 쉽게 설명하자면,

예를들어, 1 부터 100까지의 숫자 사이에서 랜덤으로 정해진 숫자 하나를 맞추는 게임을 한다고 하자.

이 때 내가 부를 수 있는 숫자의 횟수는 3회이며, 숫자를 외칠 때 마다 정답이 그 숫자보다 작은지 큰지 맞는지 확인할 수 있다. 랜덤으로 정해진 숫자는 80이고, 나는 이 정답을 모르는 상태라고 가정하자.

 

처음엔 당연히 절반인 50을 부르는게 좋을 것이다. 이 때 정답이 50보다 크기 때문에 출제자는 50보다 크다고 알려 줄 것이며 그 다음에는 50보다 작은 부분은 검사할 필요가 없다. 그래서 그 다음엔 50과 100의 절반인 75를 부른다.

만약 75보다도 크다면 또 75보다 작은 부분은 검사할 필요가 없다.

이런 식으로 절반 씩 쪼개가며 탐색할 부분을 좁혀가는 방법이다.

 

만약 순차 탐색으로 진행했다면 1부터 80까지 80번을 실행해야 하지만, 이진 탐색을 실행하면 불과 5회 정도 만에 답을 찾아낼 수 있는 것이다.

---

이 방법으로 문제를 진행해보면

1. array라는 리스트에 집들의 좌표를 입력받은 후에 정렬.

2. start = 1, end = array[-1] - array[0] 으로 설정. ( 시작값은 최소 거리, 끝 값은 최대 거리 )

3. 앞 집부터 공유기 설치

4. 설치할 수 있는 공유기 개수가 c개를 넘어가면 더 넓게 설치할 수 있다는 이야기 이므로 설치거리를 mid + 1로 설정하여 다시 앞집부터 설치.

5. c개를 넘어가지 않는다면 더 좁게 설치해야 한다는 이야기 이므로 mid - 1로 설정.

 

위의 과정을 반복실행하면 정답을 얻을 수 있다.

코드는 다음과 같다.

n, c = map(int, input().split())

array = []
for i in range(n):
    array.append(int(input()))

array.sort()


def binary_search(array, start, end):
    while start <= end:
        mid = (start + end) // 2
        current = array[0]
        count = 1

        for i in range(1, len(array)):
            if array[i] >= current + mid:
                count += 1
                current = array[i]

        if count >= c:
            global answer
            start = mid + 1
            answer = mid
        else:
            end = mid - 1


start = 1
end = array[-1] - array[0]
answer = 0

binary_search(array, start, end)
print(answer)

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !