[Python] 17371번 이사

https://www.acmicpc.net/problem/17371

---

 

24/07/05

 

 

처음 풀었을 땐 예제보고 신뢰의 제출 했는데, 증명해보려고 한다.

---

 

문제 접근 방식:

 

 

문제 제한을 보면 $N = 1000$이여서 최대 $\mathcal{O}(N^2\log N)$의 시간 복잡도로 통과할 수 있다.(해설을 읽어보니 이것이 원래 문제의도였다고 한다.)

 

문제의 요구 조건은 어떤 점 $P$에 대하여, $P$와 가장 가까운 편의 시설 $A$의 거리와 $P$와 가장 먼 편의 시설 $B$의 거리의 평균이 가장 최소가 되도록 점 $P$의 좌표를 구하는 것이다.

 

문제 예제를 잘 관찰하면 이러한 점 $P$의 좌표가 사실은 그냥 문제에서 주어진 편의 시설로 잡아도 괜찮다는 것을 알 수 있다.

 

UCPC공식 해설에서는 이를 다음과 같이 증명한다.

 

증명)

최소가 되는 점을 $P$라고 하고, $P$와 가장 가까운 편의 시설을 $A$, $P$랑 가장 먼 편의 시설을 $B$라고 하자.

또한, $A$와 가장 멀리 떨어져 있는 편의 시설을 $C$라고 하자.(최소가 되는 점 $P$가 여러 개가 될 수 있음에 유의하자)

 

문제의 요구 조건에 따라, $\overline{PA} + \overline{PB}$가 최소이다.

 

이 말은, $\overline{PA} + \overline{PB}$의 값이, 임의의 점 $P'$과 이 점과 가장 가까운 편의 시설 $A'$과 이 점과 가장 먼 편의 시설 $B'$에 대하여 $\overline{P'A'} + \overline{P'B'}$보다 더 작거나 같다라는 말과 동일하다.

 

$P$와 가장 멀리 떨어져 있는 편의 시설이 $B$이므로, $\overline{PB} \geq \overline{PC}$가 성립한다.

 

따라서, $$\overline{PA} + \overline{PB} \geq \overline{PA} + \overline{PC}$$가 성립한다.

 

$P, A, C$는 삼각부등식에 의해 다음이 성립한다.

 

$$\overline{AP} + \overline{PC} \geq \overline{AC}$$

 

따라서 위에 있는 부등식과 결합하면 $\overline{PA} + \overline{PB} \geq \overline{AC}$가 성립한다.

 

$A$와 가장 가까운 편의 시설은 $A$이다. 즉, $\overline{AA} = 0$이므로, 다음이 성립한다.

 

$$\overline{PA} + \overline{PB} \geq \overline{AA} + \overline{AC}$$

 

위에서 언급한 임의의 점 $P'$에 대한 내용을 상기해보자. 임의의 점이 $A$라면 $A$와 가장 가까운 점은 $A$고, $A$와 가장 먼 점은 $C$이다.

따라서 $\overline{AA} + \overline{AC}$의 값은 $\overline{PA} + \overline{PB}$보다 크거나 같을 수 밖에 없다.

 

위에서 증명한 부등식에 의하여 $\overline{PA} + \overline{PB}$는 $\overline{AA} + \overline{AC}$과 같음이 증명되었다.

 

이 말은, 최소가 되게 만드는 $P$가 정해진다면 그 점과 가장 가까운 편의 시설 $A$에 대해서도 똑같이 그 값을 구할 수 있고, 그 값이 $P$일 때와 동일하다는 뜻이다.

 

 

이 증명의 핵심은 문제의 정의를 다시 상기시키는 점, 가능한 점 $P$의 후보가 여러 개가 될 수 있다는 점, 그리고 삼각부등식을 활용하여 $\overline{AA} + \overline{AC}$가 사실은 $\overline{PA} + \overline{PB}$와 같아서 문제의 정의에 의해 $A$가 이러한 $P$의 후보가 될 수 있다는 점이다.

 

따라서 모든 편의 시설마다 가장 먼 편의 시설과의 거리를 구하고, 그 거리가 최소가 되도록 하는 편의 시설의 좌표를 출력하면 충분하다.

 

참고로 이런 그리디적 방식은 시복도가 $\mathcal{O}(N^2)$이다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# pakkiyatou 연습세션
import sys
input = sys.stdin.readline

N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]
MIN = 10000000000000
ans_x, ans_y = 0, 0
for i in range(N):
    M = 0
    for j in range(N):
        d = ((P[i][0] - P[j][0])**2 + (P[i][1] - P[j][1])**2)**.5
        if d > M:
            M = d
    if M/2 < MIN:
        MIN = M/2
        ans_x, ans_y = P[i]
print(ans_x, ans_y)