악곱 == 악성곱슬

이분 탐색

---

해당 문제는 이분 탐색을 이용하여 구현할 수 있는 문제이다. 입력만 작았다면 완전 탐색으로도 구현이 가능한 문제이다.

접근법

• 10억이라는 입력은 너무 크기 때문에 로그 스케일을 적용할 방법을 찾는다. 최소 몇 칸씩 건너뛰면 되는 지를 이진 탐색을 사용하여 구한다. 10억 → 5억 → 2.5억 과 같이 줄여 나간다.
• 만약 공유기를 설치할 수 있거나 남는다면 다시 범위를 늘려서 탐색한다.
• 집은 순차탐색하며 앞서 구한 거리에 따라 공유기를 직접 설치 해본다 (count_c 함수)

이렇게 한다면 O(N * log2(10억))이 된다. → 가능

import sys

def count_c(mid, n):
    prev = houses[0]
    count = 1
    for h in range(1, n):
        if houses[h] >= prev + mid:
            count += 1
            prev = houses[h]
    return count

def binary_search(start, end, c, n):
    answer = 0
    while start <= end:
        mid = (start + end) // 2
        if count_c(mid, n) >= c:
            start = mid + 1
            answer = mid
        else:
            end = mid - 1
    print(answer)

if __name__ == "__main__":
    N, C = map(int, sys.stdin.readline().rstrip().split())
    houses = list()
    for i in range(N):
        houses.append(int(sys.stdin.readline().rstrip()))
    houses.sort()
    binary_search(0, max(houses), C, N)