[백준] 2110 - 공유기 설치(이분탐색)

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

import sys
input = sys.stdin.readline
 
n, c = map(int, input().split())
arr = [int(input()) for _ in range(n)]
arr.sort()
answer = 0
 
 
def ok(val):
    count = 1
    now = arr[0]
    for a in arr[1:]:
        if a >= now + val:
            now = a
            count += 1
    if count >= c:
        return True
    return False
 
 
def binary_search(start, end):
    global answer
    if start > end:
        return
    mid = (start + end) // 2
    if ok(mid):
        answer = mid
        binary_search(mid + 1, end)
    else:
        binary_search(start, mid - 1)
 
 
binary_search(1, arr[n - 1] - arr[0])
print(answer)

이분탐색 문제이다.

처음 딱 봤을때는 "이게 왜 이분탐색이지" 할 수도 있지만, 거리 값을 이분탐색 하면서 가능한 값을 최신화하는 방식이다.

또한, 파이썬으로 풀 경우에는 입력값이 많으니 sys.stdin.readline을 사용해야 한다.

최솟값을 1로 하는 것 또한 주의해야 한다. 좌표값의 최솟값을 두면 안된다. 구하는 것은 거리의 최솟값이기 때문이다.