⚠︎ 백준 - 2110 공유기 설치

이분탐색 단계를 끝내자~

이분 탐색 단계

---

2110

⚠︎ 공유기 설치

티어 : 🥇4

분류 : 이분탐색

 

에..오

라우터 사이사이가 길게 말이지

으음

 

맨 양끝에 놓고 일단

반반 잘라가면서 반에 제일 가까운 집에다가 하나씩 놓으면?

 

근데그럼 홀짝일 때 잘라야 하는 게 다른데

그럼

홀수 개 남앗으면 하나 남은 거리 가운데에다 놓고

짝수 개 남앗으면 두개 띵띵

?아닌데

 

공유기를 중심으로 생각하지 말고

거리를 이분탐색하면서 답을 구한다고 하면~

 

오토마타공부하고다시생각해봄

졸리다

 

 

 

 

거리 크게 하고 

하나씩 보면서 기준거리 넘는 애들 하나하나 세면서 

라우터 개수가 C보다 크거나 같으면 S E 조절해서 거리 조정하기

import sys  

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

router.sort()

def binary_search(array, start, end):
    while start <= end:
        mid = (start + end) // 2
        current = array[0]
        router_count = 1

        for i in range(1, len(array)):
            if array[i] >= current + mid: # 거리가 mid 이상인 집에 설치
                router_count += 1
                current = array[i]

        if router_count >= C: ## 설치된 라우터 개수가 더 많으면 거리를 늘릴 수 있단 것
            global answer
            start = mid + 1
            answer = mid #일단 가능한상태
        else: # 설치된 라우터 개수가 작으면 거리를 더 줄여야 함
            end = mid - 1


start = 1
end = router[-1] - router[0] 
answer = 0

binary_search(router, start, end)
print(answer)

..

난 rock이다 ~~

깡깡