[백준] 2110:공유기 설치

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
house = [int(input()) for _ in range(N)]
house.sort()
min_dist = 1 # 최소 간격
max_dist = house[-1]-house[0] # 최대 간격
while min_dist <= max_dist:
    cnt = 1
    mid = (min_dist+max_dist)//2
    last_install = 0
    for i in range(1,len(house)):
        if house[last_install]+mid <= house[i]:
            cnt += 1
            last_install = i
    if C <= cnt: # 충분히 설치함. 거리를 늘려보자.
        min_dist = mid+1
    elif C > cnt: # 설치 부족. 거리 줄여.
        max_dist = mid-1
print(max_dist)

풀이 설명
1.집들의 위치를 정렬한다.
2.집 사이의 최소 간격을 2, 최대 간격을 house[-1]-house[0]로 지정한다.
3.이분 탐색을 통해 최대 거리를 구한다
-> 이때 핵심 아이디어는 마지막으로 공유기를 설치한 집의 주소를 저장(내 코드에선 last_install)하여 현재 지정한 거리(여기선 mid값) 이상 떨어진 집에 설치하는 것이다.

고민했던 부분

어떻게 처리해야 할 지 헷갈려서 고민을 많이 하게 된 부분이 있다.
바로 '정렬된 리스트에서 맨 앞에 존재하는 집이 설치되어야 하는지'이다.
결론부터 말하자면 이 문제는 맨 앞집에 반드시 공유기가 설치되어야 한다.
만약 공유기 간의 거리(d)가 주어지고 공유기의 최소 개수를 구하게 된다면 맨 앞집에 설치가 안되는 것이 유리하다.
그러나 해당 문제는 설치해야 하는 공유기 개수가 주어지고 공유기 간의 최대 거리를 구하는 문제이므로 같은 d에 대해서 공유기가 최대한 많이 설치되어야, 설치해야 하는 d가 줄어들지 않는다.