백준 2110 공유기 설치

공유기 거리 아이디어만 바로 찾으면 되었는데,
구현인줄알고 하나씩 찾아도보고 했는데 대실패~ O(N^2)이상 이라서 안되는것 같음. 1,000,000,000면 ... 힘들만 하죠..

이분탐색은 항상 어느 위치 찾기로 생각하고 있어서, 아이디어를 생각을 못한 것같다.
예를들어 12만큼의 거리를 띄워서 된다면 -> 6로도 되는거야? -> 3으로도 되는거야? -> 4으로도 되는거야? 이런식으로 확확 차이를 좁혀서 생각하는 것...

옛날의 나 어떻게 생각한거야?!ㅋㅋㅋㅋ

# 아 ... 시간초과 계속 나서 찾아봤더니... sys.stdin.readline였음...^^;;
import sys
input = sys.stdin.readline

N, C = map(int, input().split())
x_axis = [int(input()) for i in range(N)]
x_axis.sort()

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

# 공유기 거리가 이분탐색이라니... 이분탁샘은 쉬운데, 아이디어를 생각도 못했다..
while ( start <= end):
    mid = (start + end)//2
    current_x = x_axis[0]
    count =1

    for i in range(1, len(x_axis)):
        if x_axis[i] >= current_x + mid :
            count+=1
            current_x = x_axis[i]
    
    if count >= C:
        start = mid+1
        result = mid
    else: 
        end = mid-1

print(result)