백준 2110: 공유기 설치 (Binary Search / with Swift)

이분탐색을 사용하는데, 한 단계 더 깊게 생각해야하는 문제이다.

Parametric Search 형태의 문제인데, 

이미 주어진 수의 나열에서 어떤 값을 찾는 기본적인 이분탐색이 아니라, 

어떤 기준을 정하고, 그 기준에서 나온 start, end로 mid를 구하고  bs()함수에 매개변수로 전달한다!

( 이 문제에서는 우리가 구해야하는 "가장 인접한 공유기 사이의 거리"의 범위를 [1 ~ 맨 오른쪽 집과 맨 왼쪽 집 사이 거리] 로 잡고,

이 값들 사이에서 mid값을 갱신해나가면서 

모든 공유기 사이 거리가 mid값 이상일 때, 설치할 수 있는 공유기 수를 bs()함수에서 return 받고, 그 때 조건을 만족하는지 체크하는것. 

 

그 값이 c 이상이라는 것 -> 공유기 간 간격을 더 넓힐 수 있으므로, start = mid + 1

그 값이 c보다 작다는 것 -> 지금의 공유기 간 최소 간격(mid)로는 c개의 공유기를 설치할 수 없으므로, 공유기 간 최소 간격을 좁혀야한다.

                                           따라서 end = mid -1

그 값이 c라는 것 -> 바로 return하면 안되고, last변수에 저장해두고, 공유기 간 간격이 좀 더 넓어도 c개 공유기를 설치할 수 있는지 체크

                               해야한다.

[예시]

( 1, 4, 5, 7, 9 ) 이고, 3개의 공유기를 설치해야할 때,

mid = 3에서 1,4,7로 정확히 3개의 공유기를 설치할 수 있으나,

mid = 4일 때 1,5,9로 정확히 3개의 공유기를 설치할 수 있기 때문이다.