답이 되는 간격 k를 찾을 때, 순차적으로 집의 좌표를 비교하며 각각의 경우에서 최적의 해를 찾는 방법도 있을 것이다. 하지만 입력 크기( 100,000 )를 고려하나 각각의 경우에서 n번씩 비교하는 것을 생각해보면 그리 효율적인 방식은 아니다.

• binary search
  이분 탐색이란 이런 탐색 범위를 절반씩 좁혀가는 방법을 말한다.
  up down게임을 예시로 들어보겠다.

  • 1 ~ 100까지의 숫자 중 답이 되는 숫자가 60이라고 해보자.
    이분탐색의 방법으로 찾아간다면, 처음 숫자를 범위의 중간값인 50으로 불러보는 것이다.
    답이 50보다 크므로 up!!!
    이제 탐색범위는 51 ~ 100 사이로 줄어든다. 마찬가지로 범위 내 절반 값인 75를 답으로 부른다.
    down!! 탐색범위는 이제 51~ 74사이가 된다.
    이와 같은 방식으로 찾아가다보면 탐색범위는 100 -> 50 -> 25 -> 12 -> 6 -> 3 -> 1로 줄어들며 이 안에서 만족하는 답을 찾을 수 있게 되는 것!!

이분탐색은 탐색해야 할 범위가 넓을 때 활용하면 효율적으로 답을 찾아갈 수 있다. ( 절반씩 탐색하니 O(logn)의 시간 복잡도! )
이 때 보통은 중간 값이 답(출력)으로 되도록, 그리고 조건을 설정하여 탐색범위의 최소나 최대값을 조정한다.

풀이

문제에 적용해보면, 가장 인접한 공유기 거리의 최대거리를 출력하는 것이다.
만약 3개의 공유기가 각각 3,4의 간격을 가지면 출력값은 3이 된다는 것.
그렇다면 최적의 '간격'을 찾아야하므로 mid로 간격을 찾도록 해보자

그리고 만약 mid값이 답에 비해 크게 설정 됬다면, 다시말해 간격이 너무 넓게 설정이 됬다면 그 간격을 줄이는 쪽으로 하며 이는 기존범위의 최대값( max )를 조정하면 될 것!
반대로 너무 간격이 좁게 설정됬다면 간격을 넓혀야 하므로 기존범위의 최소값( min )을 조정해주면 될 것이다.

input

## input
import sys

n, c = map(int, input().split())
house = [int(sys.stdin.readline()) for _ in range(n)]

method & output

고려사항

• 탐색을 위해 먼저는 집의 좌표값들이 정렬되어 있어야 한다.
• 초기 탐색 범위의 최대 범위는 정렬된 집의 좌표의 최대값 - 최소값이면 된다.
• 공유기 수를 세기 위해 집의 좌표 중 가장 처음 좌표부터 센다.
• mid(간격)값은 여러 간격들 중 가장 인접한 간격(최소)이므로, mid보다 같거나 큰 간격에 해당하면 모두 센다.
• 이렇게 센 결과가 c보다 크면, 설치할 수 있는 공유기가 c보다 더 많다는 것으로 간격이 답보다 좁은 것이다. 반대로 c보다 작으면 간격이 답보다 크다는 것을 인지하고 구현하였다.

## method 
def sol(n, c):
    house_coor = sorted(house)
    minv = 1
    maxv = house_coor[-1] - house_coor[0] #최대 간격

    while minv <= maxv :
        opt = (minv + maxv) // 2 # 간격
        current = house_coor[0]
        cnt = 1

        for i in range(1,n):
            if house_coor[i] >= current + opt :
                current = house_coor[i]
                cnt += 1
        
        if cnt < c : # 간격이 큰 경우
            maxv = opt -1 #opt(간격)을 줄이기 위해 최댓값을 조정
        else : # 반대로 수행
            minv = opt +1
        
    return maxv

## output
print(sol(n,c))