[백준 2110 파이썬] 공유기 설치 (골드5, 이분 탐색)

알고리즘 유형 : 이분 탐색
풀이 참고 없이 스스로 풀었나요? : X

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

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

def locate(house, d, C):
    cnt = house[0]
    count = 1
    for i in range(1, len(house)):
        if house[i] - cnt >= d:
            cnt = house[i]
            count += 1
    return count
        

def findDistance(house, C):
    start = 1
    end = house[-1]
    
    while start <= end:
        mid = (start + end) // 2
        count = locate(house, mid, C)
        if count >= C:
            start = mid + 1
        else:
            end = mid - 1
            
    return end

print(findDistance(house, C))

풀이 요약

1. 이분 탐색이 필요한 이유, 이분 탐색을 어떻게 적용해야되는지가 안 떠올라 다른 사람 풀이를 보고 그 아이디어를 참고한 뒤 구현은 직접 했다.

2. 우선 이분 탐색을 쓸 때, 탐색 범위를 뭘로 잡아야하는지 알아보자.

   탐색 범위는 1부터 house[-1] - house[0] 까지의 두 공유기 사이 거리이고, 분할 조건은, 현재 단계의 거리 d에 대해 공유기 설치 횟수를 계산한 값 count를 C와 비교하는 것이다.

3. 그럼 이제 이분 탐색을 써야하는 이유를 알아보자.

   1) 순차 탐색을 쓰는 경우

   • 1부터 최대 10억까지의 모든 거리를 for로 돌면서 설치한 공유기 개수와 C가 같은지 검사를 하기 때문에 O(10^9) 정도 시간이 걸린다.

   2) 이분 탐색을 쓰는 경우

   • 우선 들어온 집의 좌표들을 정렬하기 위해, 병합 정렬로 한다고 치면 최악의 경우 O(200000*$\log_2200000$) = O(3500000) 정도이다.
     
     
   • 다음으로 1부터 최대 10억까지 거리 d를 이분 탐색하면서, 각각의 d에 대해 공유기를 설치하는 함수를 통해 설치하고, 설치 개수가 C보다 크냐 작냐로 분할해나간다. 이 때는 O($\log_21000000000$ * 200000) = O(6000000) 정도이다.
     
     
   • 즉, 이분 탐색을 쓰는 경우 최악의 경우에도 시간복잡도가 O(10^7)을 넘지 않는다.

4. 이분 탐색을 써야하는 이유와 적용하는 방식을 알았으니 구현하자.

   위에서 설명한 대로, 탐색 범위는 1부터, 가능한 두 공유기 사이 최대거리, house[-1] - house[0] 까지이다. d라고 하자.

   탐색을 하면서, d 이상의 거리를 띄우면서 공유기를 설치하는 횟수를 구하는 함수 locate를 정의하자. 이 함수로 구한 설치 횟수를 C와 비교하면서 문제를 이분 해주면 된다.

   이 때, locate로 구한 횟수 count와 C가 같은 경우는 count가 C보다 큰 경우와 같이 start = mid + 1로 설정해주면 된다.

   그 이유는, 공유기 설치 개수가 C와 같게 되는 거리 d가 여러개일 수 있기 때문이다. 만약 조건을 만족하는 d가 아직 최대값이 아니라면, 당연히 그보다 큰 d부터 다시 탐색해나가야하기 때문에, 탐색 범위에서 start를 d+1, 즉 mid+1로 설정해주는 것이다.

배운 점, 어려웠던 점

• 무엇을 대상으로 잡고 이분 탐색을 해야하는 지, 값을 어떻게 정제해서 그 값을 기준으로 분할을 해야할 지 아이디어를 떠올리는게 어려웠다.