2110번: 공유기 설치 (탐색, 이분탐색) - Fastcampus

www.acmicpc.net/problem/2110

2110번: 공유기 설치

O(NLogX) = 20만*30 = 600만

 

import sys


# 공유기 사이의 거리 (mid) => 이분탐색
def search(houses, C):
    res = 0
    start, end = 1, houses[-1] - houses[0]

    while start <= end:
        mid = (start + end) // 2
        cnt = device_cnt(houses, mid)  # 설치 가능한 공유기의 개수

        if cnt < C:
            end = mid - 1
        else:
            start = mid + 1
            res = mid

    return res


# ([1, 2, 4, 8, 9], 4) => 2개
def device_cnt(h, d):
    pos, cnt = 0, 1
    for i in range(1, len(h)):
        if h[i] - h[pos] >= d:
            cnt += 1
            pos = i
    return cnt


N, C = map(int, input().split())
houses = [int(sys.stdin.readline()) for _ in range(N)]
houses.sort()
print(search(houses, C))