250x250
Notice
Recent Posts
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
관리 메뉴

일상 코딩

[python] 백준 알고리즘 2110번 공유기 설치, 이진 탐색 풀이 본문

코딩테스트/백준 online Judge

[python] 백준 알고리즘 2110번 공유기 설치, 이진 탐색 풀이

polarcompass 2021. 11. 13. 17:48
728x90

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

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가

www.acmicpc.net

N, C = map(int, input().split())
X = sorted([int(input()) for _ in range(N)])

sta = X[1] - X[0]
end = X[-1] - X[0]

result = 0

while sta <= end:
    mid = (sta + end) // 2  # Gap을 의미함
    val = X[0]
    cnt = 1

    for i in range(1, len(X)):
        if X[i] >= val + mid:
            val = X[i]
            cnt += 1
    if cnt >= C:
        sta = mid + 1
        result = mid
    else:
        end = mid - 1
print(result)

입력 예시

5 3
1
2
8
4
9

출력 예시

3

 

728x90