백준 2110번 - 공유기 설치 - 파이썬(Python)

문제 링크

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

문제

 

 

입력 조건

•  

출력 조건

•  

 

입력 예시1

출력 예시1

입력 예시2

출력 예시2

 

풀이 전 생각

 

 

예제 코드

def binarysearch(start,end,c):
    while start<=end:
        mid = (start+end)//2
        current = arr[0]
        count = 1
        for i in range(1,len(arr)):
            if arr[i]>=current+mid:
                count+=1
                current=arr[i]
        if count < c:
            end = mid - 1
        elif count >= c:
            answer = mid
            start = mid + 1
    print(answer)
n,c = map(int,input().split())

arr = []
for _ in range(n):
    arr.append(int(input()))
    
arr.sort()
start = 1
end = arr[-1]-arr[0]

binarysearch(start,end,c)

생각

 

 

 

 

 

 

 

 

 

 

upper bound

https://www.acmicpc.net/blog/view/109

 

parametric search

https://ialy1595.github.io/post/parametric-search/

파라매트릭 서치 (Parametric Search) | ialy's blog