백준 2110 : 문제링크

  • 문제유형 :

    • 탐색

    • 이진탐색

  • 설명

    • 집의 개수 N의 최대는 200,000 이고 집의 좌표 X의 최대 1,000,000,000이다

    • 이진탐색을 이용하면 시간 복잡도는 O(N * logX)

    • 집 간 거리 Gap에 대해서 이진탐색을 한다.

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    n, c = list(map(int, input().split(' ')))`

    array = []
    for _ in range(n):
        array.append(int(input()))
    array = sorted(array)

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

    while(start <= end):    // 시간 복잡도 : O(logX)
        mid = (start + end) // 2
        value = array[0]
        count = 1
        for i in range(1, len(array)): // 시간 복잡도 : O(N)
            if array[i] >= value + mid:
                value = array[i]
                count += 1
        if count >= c:
            start = mid + 1
            result = mid
        else:
            end = mid - 1

    print(result)