[코딩인터뷰] 백준 2110번 공유기 설치

백준 2110번 공유기 설치

너무 정확하게 문제를 풀려는 습관때문에 쉽게 풀 것도 어렵게 접근하게 되는 나쁜 버릇...

import sys
rl = sys.stdin.readline

N, C = map(int, rl().split())
H = []
for _ in range(N):
    H.append(int(rl()))
H.sort()

answer = 0
# 가능한 최소 거리
lo = 1
# 가능한 최대 거리
hi = H[-1] - H[0]
while lo <= hi:
    # 허락 되는 최대 거리
    mid = (lo + hi) // 2

    # 1번 공유기를 설치한다.
    pr = H[0]
    c = 1

    for i in range(1, N):
        # 최대 거리보다 벌어지면 공유기를 설치한다.
        if H[i] - pr >= mid:
            pr = H[i]
            c += 1

    #  설치해야 하는 공유기 수보다 적게 설치했다면, 최대 거리를 좁힌다.
    if c < C:
        hi = mid - 1
    # 설치해야 하는 공유기 수보다 많이 설치했다면, 최대 거리를 늘린다.
    else:
        lo = mid + 1
        # 지금 최대 거리를 기록한다.
        answer = max(answer, mid)

print(answer)