[python3] 백준 2110 풀이 ( 공유기 설치, 이분탐색 )

저번에 푼 프로그래머스와 비슷한 문제였다. 그런데 상당히 헤매고 풀었기 때문에 다시 한번 풀이를 정리해 본다.

[python3] 프로그래머스 징검다리 풀이 ( 이분탐색 )

우선 문제를 읽어보자

문제를 읽어보면 입력으로 x가 0~1,000,000,000의 범위를 가진다. 딱 보자마자 완전 탐색으로는 절대 돌수가 없다. 따라서 이분탐색의 냄새가 난다.

x의 좌표에서 이분탐색의 느낌이 나는데, 우리는 출력으로 두 공유기 사이의 최대 거리를 출력해야한다. 공유기 사이의 최대거리를 만족하기 위해서는 2가지가 필요하다.

1. 최대값 x가 존재할때 x보다 긴 거리에 공유기 설치
2. 집에서 C만큼 공유기 설치

=> 말이 이상하긴 한데, 결국 공유기의 개수와 최대거리를 만족해야한다. 그럼 최대거리를 이분탐색으로 놓고 공유기를 만족하는지 연산을 진행하면 쉽게 구할 수 있다.

N,C = map(int, input().split())
house = []
for _ in range(N):
    house.append(int(input()))
house.sort()
L=1
R=house[-1]//2
H=0
while L<=R:
    M = (L+R)//2

    install = 1
    install_list = [house[0]]
    for i in range(1,N):
        if (house[i] - install_list[-1] >= M):
            install_list.append(house[i])
            install += 1
    if install >= C:
        H = M
        L = M+1
    else:
        R = M-1
print(H)