백준 2110. 공유기 설치
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
마찬가지로 이분탐색 문제.
일단 이분탐색할 기준은 가장 인접한 두 공유기 사이의 최대거리로 설정한다.
예를들어 가장 인접한 두 공유기 사이의 최대거리를 4라고 가정하고 해당 거리 이상을 두고 설치할수 있는 모든 공유기를 설치해본 후에,
설치해야하는 공유기의 수 C보다 많이 설치했다면 -> 간격을 더 늘릴 수 있다
적게 설치했다면 -> 간격을 더 줄여야 한다.
설치해야하는 공유기 수 C: 3
1 2 4 8 9
최소간격은 1, 최대 간격은 9-1=8 이므로
left = 1, right = 8, mid = 4
4를 기준으로 공유기를 설치해본다.
집1에 설치하고 다음집 2에 설치하면 간격은 1, 기준 간격인 4보다 작으므로 설치 불가.
집1에 설치하고 집4에 설치한다면 간격은 3, 기준 간격인 4보다 작으므로 설치 불가.
집1에 설치하고 집8에 설치한다면 간격은 7, 기준간격인 4보다 크므로 설치 가능.
설치: (1, 8)
집8에 설치되어 있고 집9에 설치한다면 기준 간격인 4보다 작으므로 설치 불가.
최종적으로 설치 된 공유기: (1,8)로 2개 설치됨. 3개 설치해야 되므로 간격을 줄여야 한다.
left = 1, right = (4-1) = 3, mid = 2
간격 2를 기준으로 공유기 설치.
집1에 설치하고 다음집 2에 설치하면 간격은 1. 기준 간격인 2보다 작으므로 설치 불가.
집1에 설치하고 집 4에 설치하면 간격은 3. 기준 간격인 2보다 크므로 설치 가능.
설치: (1, 4)
집4에 설치되어있고 집8에 설치하면 간격은 4. 기준간격인 2보다 크므로 설치 가능.
설치: (1, 4, 8)
집8에 설치되어있고 집9에 설치하면 간격은 1. 기준간격인 2보다 작으므로 설치 불가.
최종적으로 설치 된 공유기: (1, 4, 8)로 3개 설치됨.
목표 설치 공유기 갯수인 3개를 충족했지만 간격을 더 늘릴 가능성 있으므로 계속 진행.
left = (2+1) = 3, right = 3, mid = 3
간격3을 기준으로 공유기 설치.
집1에 설치하고 집2에 설치하면 간격은 1. 기준 간격이 3보다 작으므로 설치 불가.
집1에 설치하고 집4에 설치하면 간격은 3.기준 간격인 3이므로 설치.
설치: (1, 4)
집4에 설치되있고 집8에 설치하면 간격은 4. 기준 간격인 3보다 크므로 설치 가능.
설치: (1, 4, 8)
집8에 설치되있고 집9에 설치하면 간격은 1. 기준 간격은 3보다 작으므로 설치 불가.
최종적으로 설치 된 공유기: (1, 4, 8)로 3개 설치됨.
목표 설치 공유기 갯수인 3개 충족. 여기서 간격을 더 늘리면 left=(3+1)=4, right=3이므로 left가 right보다 커지므로 불가능.
가장 인접한 두 공유기 사이의 최대거리 = 3