이분 탐색. [2110]

[1. 문제 설명]

일렬로 늘어선  N개의 집들에

C개의 공유기를 설치할 때 

 

가장 인접한 두 공유기 사이의 거리의 최대 값 

 

[2. 풀이 접근]

A. 잘못된 접근

처음 이 문제를 보고 잘못 이해해서, 예제로 나온 답이 어떻게 나왔는지 이해하지 못했다.

왜냐하면, 1,2,9 이렇게 설치하면 두 공유기 사이의 최대 거리는 7이 나오기 때문이다.

두 공유기 사이 거리의 최대 값에 중점을 두었기 때문이다.

여기에 한가지 조건 "가장 인접한" 을 추가해야, 내 생각이 틀렸음을 이해할 수 있었다.

위와 같은 방식으로 설치하는 경우, 

가장 인접한 두 공유기 사이의 거리는 1이 되기 때문이다.

 

B. 올바른 접근

문제에서 주어진 C 공유기의 개수는 그렇게 중요한 요소는 아니다.

중요한 요소는 공유기 사이의 거리이다.

C 가 2인 경우 공유기 사이 거리의 최대 값은 처음 집과 마지막 집 사이의 거리이다.

C 가 3인 경우 부터는 조금 복잡해진다.

 

그래서 일단, 공유기 사이 거리의 최소와 최대를 고민해본다.

최소값의 후보는 1 => min

최대값의 후보는 처음집과 마지막 집 사이의 거리이다. => max

 

이제 범위 [min, max] 에 대해서 이분 탐색을 적용한다.

그런데 여기서 중요한 점은 두 범위의 중간 값은

두 공유기 사이 거리의 하한 값이라는 것이다.

 

하한 값 보다 1 이라도 큰 것은 중요하지 않다.

가장 인접해있지 않기 때문이다.

 

나머지는 코드를 통해 정리하도록 한다.

 

 

[3. 코드]