BOJ 2110. 공유기 설치 (Gold 4) / 이분탐색 조건 설정

🔎 BOJ 2110. 공유기 설치 (Gold 4)

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

2110번: 공유기 설치

 

💡 SOL

import sys
from bisect import bisect_left
input = sys.stdin.readline

N, C = map(int, input().split())  # N 집 수 C 공유기 수
X = [0] * N
for i in range(N):
    X[i] = int(input())
X.sort()

left = 1
right = X[-1] - X[0]
ans = 1
middle = (left + right) // 2
while left <= right:
    middle = (left + right) // 2
    target = X[0]
    cnt = 1
    for i in range(1, len(X)):
        if X[i] >= target + middle:
            cnt += 1
            target = X[i]

    if cnt >= C:
        left = middle + 1
        ans = middle
    else:
        right = middle - 1
print(ans)

 

💭 TIL

# TIL

이분탐색 조건 설정하기 어려워........

다음에 다시 봐야지