[BOJ 17371] 이사 | 증명

BOJ 17317 이사의 증명

 

문제: 점 $P_1$, $P_2$, ... $P_N$이 주어질 때 $f(X)$를 점 $X$에 대해 $P_i$중 가장 먼 점과 가장 가까운 점의 거리의 합으로 정의하자. $min(f(X))$를 구하시오.

 

Claim)

$min(f(P_i)) = min(f(X))$

= $X$를 $P_i$ 중 하나로 정해도 그 최솟값은 전체 최솟값과 같다.

 

Proof) 

$f(P_{opt}) = min(f(P_i))$ 

$f(X_{opt}) = min(f(X))$

$X_{opt}$에 대해 가장 가까운 점 $P_i$와  가장 먼 점 $P_j$.

 

삼각부등식에 의해 $\overline{X_{opt} P_i} + \overline{X_{opt} P_j} \geq \overline{P_i P_j}$

증명은 $X$를 $P_i$로 옮기는 것에서 끝나지 않는다.

$P_i$에서 가장 먼 점이 $P_j$가 아닐 수도 있기 때문.

 

$P_i$에서 가장 먼 점을 $P_k$라 하자.

$\overline{X_{opt} P_j} \geq \overline{X_{opt} P_k}$와 삼각부등식에 의해

$f(X_{opt}) = \overline{X_{opt} P_i} + \overline{X_{opt} P_j} \geq \overline{X_{opt} P_i} + \overline{X_{opt} P_k} \geq \overline{P_i P_k} = f(P_i) \geq f(P_{opt})$

 

$min(f(P_i)) = f(P_{opt}) \leq f(X_{opt}) =min(f(X))$

$\{P_i\} \subset \{X\}$이므로  $min(f(P_i)) \geq min(f(X))$

 

$\therefore min(f(P_i)) = min(f(X))$