이진 탐색(이분 탐색): 백준 2110 파이썬

문제:

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

2110번: 공유기 설치

풀이:

이 문제는 처음에 이해하기가 다소 어려웠다. 문제에서 집 좌표의 범위가 (0 ≤ x ≤ 1,000,000,000)와 같아서 이진 탐색을 사용해야 하겠다는 생각은 들었지만, 찾아야 하는 수 target을 어떤 것으로 할지 떠오르지 않았다. 구글링을 해서 힌트를 얻어 문제를 풀 수 있었다. 이 문제는 이진 탐색의 방법을 응용해서 해결하는 문제로 따로 target이라는 것이 없다.

해결 과정은 다음과 같다.

 

1.  집과 집 사이의 거리 최솟값 1을 start, 집과 집 사이의 거리 최댓값을 end로 초기화해준다. (문제에서 집 여러 개가 같은 좌표를 가질 수 없다고 했으므로 최솟값은 1, 최댓값은 입력받은 집들의 좌표를 정렬한 후 0번 인덱스와 n-1번 인덱스와의 차이)
2. start와 end를 가지고 mid값을 구하고 해당 mid 값을 공유기 사이 거리의 최솟값으로 정했을 때 주어진 집 좌표에서 공유기를 총 몇 개 설치할 수 있는지 구한다.
3. 만약 공유기를 c개 보다 적게 설치 할 수 있다면 공유기 사이의 거리가 먼 것이기 때문에 end를 mid-1로 변경하여 사이의 거리 mid를 작게 해 준다.
4. 공유기를 c개 보다 많거나 같게 설치할 수 있다면 공유기 사이의 거리가 가까운 것이기 때문에 start를 mid + 1로 변경하여 거리 mid를 크게 해 주고, 리스트 'result'에 추가를 해준다.
5. 마지막으로 리스트 'result'에 저장된 수 중 가장 큰 값을 출력해준다.

 

정답:

import sys

n, c = map(int, sys.stdin.readline().split())
house = [int(sys.stdin.readline()) for _ in range(n)]

house.sort()

# 공유기 사이 거리 최솟값
start = 1 
# 공유기 사이 거리 최댓값
end = house[n-1] - house[0]
result = []

while start <= end:
    count = 1
    mid = (start + end) // 2
    current = house[0] # 공유기가 설치된 집의 위치 
    for x in house:
        if current + mid <= x: # 공유기 설치
            count += 1
            current = x 
    if count >= c: # mid 값에 따라 설치된 공유기의 개수가 c 보다 많거나 같으면
        start = mid + 1 # 거리를 늘린다.
        result.append(mid)
    else:
        end = mid - 1 # c 보다 작으면 거리를  줄인다.

print(max(result))