[백준 2110] 공유기 설치

1. 문제

www.acmicpc.net/problem/2110

2110번: 공유기 설치

2. 접근 방법

이진탐색을 해야합니다.

3. 코드

import sys
N, C = map(int, sys.stdin.readline().rstrip().split())
nums = []
for _ in range(N):
    nums.append(int(sys.stdin.readline().rstrip()))
nums.sort()

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

while (start <= end):
    mid = (start + end) // 2
    val = nums[0]
    cnt = 1
    for i in range(1, N):
        if nums[i] >= val + mid:
            val = nums[i]
            cnt += 1
    if cnt >= C:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)

4. 마치며

참고로 sys와 sys를 쓰지 않는 것은 엄청난 시간 차이를 보여줍니다 ,, 후우 ~!

무려 6배나 ..!