[백준 파이썬] 2110 공유기 설치

 

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

2110번: 공유기 설치

문제

 

지정된 공유기 개수를 설치했을 때 가장 인접한 두 공유기 사이의 거리를 최대로 하는 문제이다.

---

 

아이디어

집의 좌표의 최대 개수가 1,000,000,000이므로 이를 완전탐색으로 풀려고하면 시간초과가 나오게 된다.

따라서 이분탐색을 이용하여 해결하였다.

 

이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

 

풀이

이분탐색을 적용할 부분은 바로 공유기의 개수이다.

 

먼저 집들간의 거리중 중간 값의 거리를 구한다

예를들어 1, 2, 4, 8, 9 로 집의 좌표가 나와있을 경우

1 + 8 // 2 -> 4 로 중간값을 구한다.

이 대 배열의 중간값으로 구하지 않는 이유는 공유기간의 거리를 기준으로 구해야하기 때문이다.

home = []
for i in range(N):
    home.append(int(input()))

home.sort()

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

 

이 후 다음과 같은 기준으로 공유기를 설치한다.

이전 집의 위치와 현재 집의 위치의 거리의 차이가 구한 중간값보다 클 경우에만 공유기를 설치한다.

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

 

그 다음 이분탐색을 사용하는데

설치한 공유기가 C(설치해야하는 공유기의 수)보다 클 경우와 작을 경우를 나누어 탐색을 진행한다.

if wifi >= C:
            global result
            start = mid + 1
            result = mid
        else:
            end = mid - 1

 

최종적으로 result값을 출력한다.

 

 

코드

N, C = map(int,input().split())
home = []
for i in range(N):
    home.append(int(input()))

home.sort()

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

result = 0

def binarySearch(home, start, end):
    while start <= end:
        mid = (start + end) // 2
        current = home[0]
        wifi = 1
        
        for i in range(1, len(home)):
            if home[i] >= current + mid:
                wifi += 1
                current = home[i]
        
        if wifi >= C:
            global result
            start = mid + 1
            result = mid
        else:
            end = mid - 1

binarySearch(home, start, end)
print(result)