[백준] 2110번-공유기 설치 (Python)

 

알고리즘 분류)

이분탐색, 매개 변수 탐색

*매개 변수 탐색(Parametric Search): 이분 탐색을 사용하여 조건을 만족하는 최대값을 구하는 방법이다.

*Parametric Search의 Detail은 https://stopmin.tistory.com/31 여기 정리해 놨음.

 

Solution)

이진탐색의 정의에 맞게 일단 비교해야 하는 값들을 sorted해서 House에 정리해줬다.

start, end 포인트를 1과 가장 멀리 떨어져있는 집 사이의 거리로 설정했다.

 

그리고 이제 while (start <= end)... 해서 이분탐색을 쫙 돌려주는데 이 while문 안 쪽 코드 짜는게 빡세다.

일단 기준점이 필요하다. house[0]을 기준으로 삼고, 일단 최소 거리 1이니 count = 1로 잡는다.

그리고 for문을 돌린다. 집의 개수까지 돌리는데 만약 집의 거리가 기준점+중간값 보다 크거나 같다? => count  += 1로 간다.

그리고 if count 가 C보다 커질 경우에는 (start+end)값이 작기 때문이기에 start point를 mid + 1로 바꿔준다. 그리고 result = mid값이 된다. 만약 C보다 작을 경우에는 end값을 mid -1로 만들어주면 된다.

 

Code)

import sys
N, C = map(int,sys.stdin.readline().split())
house = [int(sys.stdin.readline()) for _ in range(N)]
house = sorted(house)

start = 1
end = house[-1] - house[0]
result = 0

while (start <= end):
    mid  = (start+end) // 2
    mile = house[0]
    count = 1
    for i in range(1,N):
        if house[i] >= mile + mid:
            mile = house[i]
            count += 1
    if count >= C:
        start = mid + 1
        result = mid
    else:
        end = mid - 1
print(result)