백준 공유기 설치 코드 및 해설 (파이썬)

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

2110번: 공유기 설치

 

C개의 공유기를 설치할 수 있는 가장 인접한 공유기 사이의 최대 거리를 이진탐색으로 탐색합니다. 최소 거리 min_gap을 1로, 최대 거리 max_gap은 (집 좌표 중 가장 큰 값) - (집 좌표 중 가장 작은 값)으로 설정합니다. 이후 min_gap과 max_gap의 중간값인 mid_gap을 구하며 다음을 반복합니다.
mid_gap일 때 설치 가능한 공유기 개수를 count에 저장합니다. 이 count 값이 C 이상이면 거리를 늘릴 수 있으므로 min_gap을 mid_gap + 1 값으로 갱신합니다. 그리고 현재 mid_gap 값을 answer로 저장합니다. 반대로 count 값이 C보다 작은면 거리를 좁혀야 하므로 max_gap을 mid_gap - 1 값으로 갱신합니다. 이를 min_gap이 max_gap보다 작거나 같을 때까지 반복합니다.
while문을 탈출한 후 answer를 최종 정답으로 반환합니다.

 

https://codlingual.tistory.com/189

이진 탐색

 

import sys

# 입력 받아오기 
inputs = list(map(int, sys.stdin.read().split()))

# 집의 개수
N = inputs[0]
# 설치할 공유기의 개수 
C = inputs[1]
# 집의 좌표들
homes = inputs[2:]

# 오름차순으로 정렬
homes.sort()

# 최대 떨어진 거리
max_gap = homes[-1] - homes[0]
# 최소 떨어진 거리 
min_gap = 1 
answer = None

# 이진 탐색 
while min_gap <= max_gap:
    # 떨어진 거리의 중간값 
    mid_gap = (max_gap + min_gap) // 2
    
    # 현재 공유기를 설치한 집의 좌표 
    current = homes[0]
    # mid_gap에 따라 설치할 수 있는 공유기의 개수 
    count = 1
    
    for i in range(1, N):
        # 직전에 설치한 공유기보다 mid_gap 이상 떨어진 곳에 공유기 설치
        if homes[i] >= current + mid_gap:
            current = homes[i]
            count += 1 
    
    # C 이상의 공유기를 설치할 수 있는 경우 
    if count >= C:
        # 격차를 늘림 
        min_gap = mid_gap + 1 
        # 현재 격차를 answer로 중간 저장 
        answer = mid_gap
    # C보다 적은 공유기만 설치할 수 있는 경우 
    else:
        # 격차를 줄임 
        max_gap = mid_gap - 1 

print(answer)