일상 코딩
[python] 백준 알고리즘 2110번 공유기 설치, 이진 탐색 풀이 본문
728x90
https://www.acmicpc.net/problem/2110
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
'코딩테스트 > 백준 online Judge' 카테고리의 다른 글
[python] 백준 알고리즘 1236번 성 지키기, 배열 회전, max() (0) | 2021.11.13 |
---|---|
[python] 백준 알고리즘 1302번 베스트셀러, sorted()를 이용한 풀이 (0) | 2021.11.13 |
[python] 백준 알고리즘 1543번 문서 검색, 리스트 슬라이싱을 활용한 풀이 (0) | 2021.11.12 |
[python] 백준 알고리즘 7490번 0 만들기, 중복순열 풀이법 (0) | 2021.11.11 |
[python] 백준 알고리즘 1074번 Z, 다이나믹 프로그래밍 풀이법 (0) | 2021.11.10 |