공유기 설치
Prob
N개 집에 C개 공유기를 가장 인접한 두 공유기 사이 거리가 최대가 되도록 설치
Solv
집이 겹칠 수는 없으니 low=1
high는 집 사이의 최대 거리로 설정
이분 탐색으로 C를 맞춰나가다보면 답 도출 가능
사용한 공유기 갯수인 n을 C와 비교
mid를 설치 기준점으로 두고 두 공유기 사이가 기준점을 넘으면 n++
n\(>=\)C인 경우 high = mid-1
n\(<=\)C인 경우 low = mid+1
low > high 일때까지 반복
Check
N=5 C=3
X=[1 2 8 4 9]
| low | high | st | mid | n |
|---|---|---|---|---|
| 1 | 8 | 1 | 4 | 1 |
| 8 | 2 | |||
| 1 | 4-1 | 1 | 2 | 1 |
| 4 | 2 | |||
| 8 | 3 | |||
| 3+1 | 3 | 1 | 3 | 1 |
| 4 | 2 | |||
| 8 | 3 |
