[이분탐색] 백준 2110번 공유기 설치 with Python3 ★★

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

2110번: 공유기 설치

문제

정답 풀이

import sys
n,c = map(int,input().split())

house = []
for _ in range(n):
    x = int(sys.stdin.readline())
    house.append(x)

house.sort()

# 공유기 거리의 최소값
start = 1
#  공유기간의 가능한 최대 거리 = 가장 높은 거리와 가장 낮은 거리의 차이
end = house[-1] - house[0]

result = 0

while (start <= end):
    mid = (start+end)//2 # 해당 gap(공유기간의 거리)
    old = house[0]
    count = 1

    for i in range(1, len(house)):
        if house[i] >= old+mid: # gap 이상
            count+=1
            old = house[i]
    
    if count >=c:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)

 출처:https://assaeunji.github.io/python/2020-05-07-bj2110/https://claude-u.tistory.com/446

해설

적절한 조건을 만들 자신이 없어서 답부터 봤다.

자세한 설명이 링크에 있다. 

 

근데 설명이 조금 이상하다.

아직 완전히 이해는 못했지만, 가능한 최대 거리를 찾아가는 이분 탐색 법이다.

말은 쉬운데, 참 대단;

 

정답 풀이

x

출처:

 

해석