algorithm'''problem solve
[백준] 2110 - 공유기 설치(이분탐색)
JunHwa Park
2020. 10. 8. 11:34
https://www.acmicpc.net/problem/2110
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 �
www.acmicpc.net
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
31
32
33
34
35
|
import sys
input = sys.stdin.readline
n, c = map(int, input().split())
arr = [int(input()) for _ in range(n)]
arr.sort()
answer = 0
def ok(val):
count = 1
now = arr[0]
for a in arr[1:]:
if a >= now + val:
now = a
count += 1
if count >= c:
return True
return False
def binary_search(start, end):
global answer
if start > end:
return
mid = (start + end) // 2
if ok(mid):
answer = mid
binary_search(mid + 1, end)
else:
binary_search(start, mid - 1)
binary_search(1, arr[n - 1] - arr[0])
print(answer)
|
cs |
이분탐색 문제이다.
처음 딱 봤을때는 "이게 왜 이분탐색이지" 할 수도 있지만, 거리 값을 이분탐색 하면서 가능한 값을 최신화하는 방식이다.
또한, 파이썬으로 풀 경우에는 입력값이 많으니 sys.stdin.readline을 사용해야 한다.
최솟값을 1로 하는 것 또한 주의해야 한다. 좌표값의 최솟값을 두면 안된다. 구하는 것은 거리의 최솟값이기 때문이다.