백준 공유기 설치 : 왜 이분탐색이 가능한가?

 안녕하세요. 백준에서 chogahui05로 활동하고 있는 조경완입니다. 백준의 공유기 설치 문제는 많이 풀어보셨을 겁니다. 정확히 말하면, N개의 point가 있고, 그 중, C개를 설치하려고 할 때, 가장 인접해 있는 두 공유기 사이의 거리를 최대화 하라는 문제입니다. 어렵네요. 이를, 먼저 결정 문제로 바꾸어 봅시다.

 

 그러면, 먼저 f(x)의 값을 어떻게 구해야 할 지 생각해 봅시다.

 

 

---

 N개의 집을 x 좌표 오름차순으로 정렬했다고 해 봅시다. 그러면 첫 공유기는 어디에 설치해야 할까요? 1번째 집에 설치해야 합니다. 왜 그럴까요? 문제 조건에 따르면, 같은 x좌표를 가지는 집은 없다고 했습니다. 그렇기 때문에, 집이 n개가 있고, i번째 집의 위치를 x[i]라고 하면, 아래의 식이 성립합니다.

 

 이는 집의 위치를 오름차순 정렬하였기 때문입니다. Q(t)를 다음과 같이 정의하겠습니다.

 

 

 이제, 아래 L1을 증명해 봅시다.

 

 이것을 어떻게 증명해 볼까요?

 

 일단, x[0] = -inf, x[n+1] = inf라고 하고, inf가 20억이라면, 입력으로 주어진 임의의 집의 좌표 x'에 대해서 다음을 만족합니다.

 

 

 

  x[i] < a <= x[i+1]을 만족하면, Q(a)의 값은 i+1입니다. 예를 들어, 정렬이 된 x 배열이 다음과 같다고 해 봅시다.

 

 

 Q(4)의 값은 얼마인가요? x[2] < 4 <= x[3]을 만족하므로, 3임을 알 수 있습니다. a < b라면, x[i] < b임을 알 수 있습니다. 최소한, b는 x[i]보다 클 겁니다. 만약에, 그렇지 않다고 해 봅시다. 즉, x[i'] < b <= x[i'+1]이라고 합시다. 그리고 i'+1 < i+1 라고 해 봅시다. 그러면 i' + 1이 정수이기 때문에, i'+1은 i보다 작거나 같을 겁니다.

 

 분명한 것은 a < b라고 했는데, b < a다. 모순의 관계가 나와버렸다는 것입니다. 따라서, a<b이면, Q(a)<Q(b)입니다. 이 L1을 가지고, 다음 명제들도 증명해 보겠습니다.

 

 

---

 명제 L2는 다음과 같습니다. 공유기가 떨어져야 하는 최소 거리를 dist라고 합시다.

 

 쉽지 않네요. 역으로, 최적해가, 맨 처음에 1번째 집이 아닌 다른 집을 택한 것이라고 해 봅시다.

 

 

 그 때 최적해 중 일부를 노란 색으로 칠해보았습니다. 분명한 것은 x[sec] - x[first]의 값은 dist보다 크거나 같다는 것입니다. x[first]는 x[1]보다 큽니다. 그러면, 다음 관계식이 성립합니다.

 

 그러면 이렇게 선택해도 됩니다.

 

 

 역시 최적해입니다. 그러면, 1번을 택하고 난 다음에는 어떤 집을 택하는 게 최대한 많은 공유기를 설치하는 전략일까요?

 

 

 x[1] + dist보다 크거나 같아지는 최초의 location 값을 u라고 할 때, u번째 집을 택하는 것이 이득입니다. 즉, x[i]의 값이 dist + x[1]보다 크거나 같은 i의 범위가, u <= i라고 할 때. 2번째로 선택할 수 있는 집의 집합은 아래와 같습니다. 근데 왜 하필 u번째 집을 택해야 하나요?

 

 

 어떤 것을 택해야 최적인지는 마찬가지 방법으로 증명하시면 됩니다.

 

 

---

 그러면, 아래 명제 L3을 증명해 보겠습니다.

 

 왠지 맞는 것 같지만 그냥 증명하기는 어려우니, a < b이면, f(a) < f(b)라고 해 봅시다. 즉, 인접한 공유기의 최소 거리를 더 멀리 했을 때, 더 많이 설치할 수 있다고 해 봅시다.

 

 

 인접한 공유기 사이의 최소 거리가 b일 때 상황입니다. 이 때 답이 K개를 설치할 수 있다. 라고 하면, 구간 [2, K]에 속한 임의의 i에 대해서, x[s(i)] - x[s(i-1)]은 b보다 크거나 같습니다. 그런데 b는 a보다 크기 때문에, x[s(i)] - x[s(i-1)]의 값은 a보다 크거나 같다는 명제 또한 참입니다.

 

 즉, 최소 거리를 a개로 놓았을 때, 적어도 b개로 놓았을 때만큼 설치할 수 있습니다. 즉, 인접한 공유기의 최소 거리를 더 멀리 설치했을 때, 가까이 설치했을 때 보다 더 많이 설치할 수 있다는 말은 거짓입니다. 따라서, L3은 참입니다. f가 단조 감소, 혹은 단조 증가의 특성을 보입니다. 따라서, 이분 탐색을 적용할 수 있습니다. 이 질문에 대해서, 졸업하기 전 마지막 기말고사를 보기 전에 급하게 단 감이 있어요. 이 글과 비슷한 맥락이니 답변 참고하셔도 좋을 듯 싶습니다. 갑자기 저 답변에 좋아요가 많이 달리긴 하네요.