이 문제가 원하는 것은 나올 수 있는 최소거리(인접한 두 공유기의 거리) 중에서 최댓값을 구하는 것, 좀 더 구체적으로 말하면 최소거리 이상으로 모든 공유기가 떨어져 있어야 하고 설치된 공유기가 C개여야 한다. 또한 여러개의 상황이 만들어질 수 있는데 이 중에서 가장 큰 최소거리를 선택해야 한다.
예를 들면 ‘공유기간 최소거리가 5일때, 공유기 3개를 설치할 수 있는가?’ 라는 질문이 이 문제를 푸는 핵심 아이디어이다.
문제의 입력출력 예시를 사용하고 최소거리가 4일때, ‘1 2 4 8 9’ 에서 순차적으로 공유기를 넣으면 1 그리고 8(직전에 공유기를 설치한 1과 7만큼 떨어져 있으니까) 그 다음 적어도 12(직전에 공유기를 설치한 8과 최소 4만큼 떨어져야 하니까) 이상이 되어야 하는데 9까지 밖에 없으므로 공유기는 2개만 설치할 수 있다. 따라서 문제예시에서는 C가 3이므로 최소거리가 4가 될 수 없다.
따라서 이런 방식으로 계속 최소거리를 8부터 1까지 역순으로 설정해야 하는데, 그냥 반복문을 사용한 선형탐색으로 진행하면 최소거리를 설정하고(N-1번) 공유기를 설치하는데(N번) O(N * N)으로 시간초과가 날 수 있기 때문에 최소거리를 설정하는 것을 이진탐색으로 해야 한다.
즉 start 1, end 8, mid 4로 했을때 공유기를 C개 설치하지 못하면 → mid를 줄여야 하므로 end를 이전 mid-1인 3로 만들어서 mid를 2로 설정하고 시뮬레이션 → 공유기 C개를 설치할 수 있으면 mid를 늘려야 하므로 start를 mid+1인 3으로 만들어서 중간점을 늘리고 다시 시뮬레이션→ 공유기를 C개 설치할 수 있는 중간점 중 가장 큰 값을 답으로 설정. 이분탐색을 통해 최소거리를 구하는데, 후보도 되지 못하는 값(위의 경우 4)보다 큰 경우는 어짜피 안되는 경우이므로 제외하기 위해 start와 end값을 조정한다.