[백준] 공유기 설치
이진탐색
백준
medium
문제
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
2 3 1
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
3
이진탐색으로 최대 GAP을 구한다.
- c개의 공유기를 최대 얼마만큼의 gap으로 n개의 집에 설치할 수 있냐는 문제
- n개의 집의 크기가 10억개이므로 O(logn)의 시간 복잡도가 필요
- 구하고자 하는 gap은 최소, 최대로 중간값 mid로 설정할 수 있다.
- 따라서 mid로 이진탐색하여, 그 gap으로 집에 c 만큼의 공유기를 설치할 수 있는 지 확인한다.
이진탐색
재귀 또는 반복문으로 구현 가능하다. 되도록이면 반복문으로 구현한다.
이진탐색은, 탐색해야 하는 값들이 너무 많으면 반씩 나눠서 탐색하는 기법으로 사용한다.
- 탐색하는 모수를 반으로 줄이는 것이 아니라 가능한 answer를 최소 최대를 설정하고 mid 값으로 이진탐색을 하며 이 값이 조건에 만족하는 값인지 확인하는 방법이다.
start = array[1] - array[0]
end = array[-1] - array[0]
result = 0
while start <= end:
mid = (start + end) // 2
value = array[0] # 첫번째 집에서부터 거리를 탐색한다.
count = 1 # 첫번째 집에 공유기를 놓았다고 가정한다.
for i in range(1, len(array)):
if array[i] >= mid + value:
value = array[i]
count += 1 # 공유기를 설치한다.
if count == c:
break
if count == c: # 해당 mid(gap)으로 c개의 공유기를 설치할 수 있다면, gap을 하나 늘려본다.
start = mid + 1
result = mid
else: # 공유기를 설치할 수 없을 경우, gap을 줄여본다.
end = mid - 1