코딩테스트/백준 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