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

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

2110번: 공유기 설치

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
houses = []
for _ in range(n):
    houses.append(int(input()))
houses.sort()

left = 1
right = houses[-1] - houses[0]
result = 0

while left <= right:
    mid = (left + right) // 2 # 설치 간격
    set_position = houses[0]  # 설치 장소
    count = 1

    for house in houses:
        if house >= set_position + mid:
            count += 1
            set_position = house

    if count >= c:
        left = mid + 1
        result = mid
    else:
        right = mid - 1

print(result)

이분탐색 문제이다.

left와 right를 각각 최소 간격과 최대 간격으로 할당후,

그 값들을 기준으로 mid 값을 계산한다.

그 이후에 left <= right의 조건이 만족하는 동안 while 문을 반복하며 가장 인접한 두 공유기 사이의 최대 거리를 구하는 건데, 

 

if house >= set_position + mid:

위 조건이 만족한다는 의미를 공유기를 설치 할 수 있다는 의미이다.

공유기를 설치할 수 있으면 count를 += 1 해준다.

 

if count >= c:
    left = mid + 1
    result = mid
else:
    right = mid - 1

위 코드에서 count가 c 보다 같거나 크다는 의미는 최대 간격으로 설치했거나, 혹은 최대 간격보다 좁게 설치했다는 의미이므로 left의 값을 더 크게 할당해주어 간격을 더 넓힌 상태로 탐색을 다시 하게 한다.