공유기 설치 [백준 2110]

문제

---

공유기 설치 [백준 2110]
https://www.acmicpc.net/problem/2110

풀이

---

처음에 이 문제를 보고 이진 탐색 개념인 걸 알았지만 어떻게 풀 지 감이 안잡혔었다. 해서 시간 초과가 나더라도 순차적 탐색을 해보자라는 생각으로 combination 함수를 이용하여 여러 집을 c개수 만큼 조합으로 선택하고 그 리스트들의 값 차이를 저장, 그 중 가장 작은 수들의 집합에서 가장 큰 수를 출력하는 코드를 짰다. 당연히 백준 채점에선 시간 초과가 났다.
이진 탐색을 이용해보자 해서 생각한 것은 가장 큰 간격과 가장 작은 간격을 정하여서 중간 간격으로 집에 공유기를 설치했을 때 설치할 수 있는 공유기 수와 c와 비교하여 c가 더 크면 간격을 줄이고 반대의 경우엔 크게 해서 코드를 짰다.

코드

---

n, c = map(int, input().split())
arr = [int(input()) for _ in range(n)]
arr.sort()

def binary(arr, start, end, result):
    if start > end:
        return result
    mid = (start + end) // 2
    value = arr[0]
    count = 1
    for i in range(1, n):
        if arr[i] >= value + mid:
            value = arr[i]
            count += 1
    if count >= c:
        return binary(arr, mid + 1, end, mid)
    else:
        return binary(arr, start, mid - 1, result)
    
print(binary(arr, 1, arr[n - 1] - arr[0], 0))