2110번 공유기 설치(이분탐색) - ☆

#문제링크 : https://www.acmicpc.net/problem/2110

<전략>

1. 가장 인접한 두 공유기의 최대 거리를 구하려면, "첫 집과 끝집 사이의 거리"(주어진 집들 사이의 간격중 가장 큰 간격)와 거리 1의 중간값(mid)를 우선 구한다. 거리 1로 시작하는 이유는 중복되는 집이 없으므로, 모든 집들 사이의 간격은 최소한 1이상이기 때문이다. 가장 간격이 작은 거리 기준을 start(지금은 거리 1), 가장 간격이 큰 거리 기준을 end(지금은 첫집과 끝집사이의 거리)라 하자.

2. 각각 이웃한 집사이의 간격을 확인하면서 mid보다 같거나 크면 카운트(cnt)를 늘려준다.

3. 만약, 카운트(cnt)가 공유기의 갯수(C)보다 작다면, mid값이 너무 커서, 즉, 집간의 간격을 너무 넓게 잡아서 공유기를 채 다 설치하지 못하는 것이다. 따라서, 이때엔, end(끝집의 기준)을 mid-1로 잡고 새롭게 측정해볼 간격을

mid = (start + end) / 2

로 계산하여 범위를 좁혀간다. 반대로, 카운트(cnt)가 공유기의 갯수보다 같거나 크다면, 집간의 간격을 너무 좁게 잡거나 딱 맞을 수 있는 경우이므로, start = mid +1로 해준다. 만약, 지금 mid간격이 좁다면, 간격을 더 넓히는 의미이고, 지금 mid간격이 딱 맞는다면 이땐, start값을 더 높게 가져가서 결국 start==end 가 될때까지 mid간격이 줄어들었다 커졌다 반복할 것이다. 최종적으로 start==end 가 되었을 때, 주어진 집 간격중 최대 값이 start==end==mid가 될 것이고, 같거나 크면 start값이 +1이 되어 while문 조건에서 벗어나는 조건이 되므로, 반복문을 빠져 나온다.

결국, end나 mid값을 출력하면 정답이 된다.

※주의사항

1. 이분탐색의 원리와 문제에서 요구하는 알고리즘이 어떤 건지 잘 매칭해본다.

Code