모든 좌표 쌍의 맨해튼 거리의 합을 효율적으로 구하는 방법

1. 문제

 

21203번: Distance (acmicpc.net)

21203번: Distance

 

2. 풀이

 

n 제한이 20만이라 모든 좌표쌍 일일이 정해서 거리를 구해보는 방법으로는 어림도 없다

 

https://www.geeksforgeeks.org/sum-manhattan-distances-pairs-points/

Sum of Manhattan distances between all pairs of points - GeeksforGeeks

 

조금 다른 방법으로 어떤 점 $(x_{i}, y_{i})$에 대하여 다른 점 (x,y)와의 맨해튼 거리 합을 나타내보면...

 

$$|x_{i} - x_{0}| + |x_{i} - x_{1}| + ... + |x_{i} - x_{i-1}| + .... + |y_{i} - y_{0}| + |y_{i} - y_{1}| + ... + $$

 

x좌표만 따로 본다면..

 

$$|x_{i} - x_{0}| + ... + |x_{i} - x_{i-1}| + ... $$

 

만약 x좌표만 오름차순으로 정렬한다면 $x_{0} < x_{1} < x_{2} ... < x_{n}$이 된다고 할때,

 

0번부터 i-1번까지 x좌표는 i번 x좌표보다 작으므로...

 

$$i * x_{i} - (x_{0} + x_{1} + ... + x_{i-1}) = i * x_{i} - S_{i-1}$$

 

 

그러므로, 최초 $S_{0} = x_{0}$로 정의해놓고, i = 1부터 n까지 순회한다.

 

i = 1에 대해 $1 * x_{1} - S_{0}$를 더하고, $S_{0}$에는 $x_{1}$을 더하여 $S_{1}$으로 만들어준다.

 

그러면 i = 2에 대해 $2 * x_{2} - S_{1}$을 바로 구할 수 있다. 그리고 $S_{1}$에는 $x_{2}$를 더하여 $S_{2}$로 만들어준다.

 

이를 i = n까지 반복하면 된다.

 

 

y좌표도 마찬가지로 생각할 수 있다.

 

#sum of manhattan distance between all pairs of points
from sys import stdin

def distance(x1,x2,y1,y2):
    
    # always x2 > x1, y2 > y1
    return x2-x1 + y2-y1

n = int(stdin.readline())

x_points = []
y_points = []

for _ in range(n):
    
    x,y = map(int,stdin.readline().split())

    x_points.append(x)
    y_points.append(y)

answer = 0

#i번과 나머지 0,1,2,...,i-1번끼리 맨해튼 거리의 합은..
#|xi - x0| + |xi - x1| + ... +|xi - x(i-1)| + |yi - y0| + ... + |yi - y(i-1)|

#x,y좌표 각각 정렬해둔다면.. x0 < x1 < x2 <... <xn, y0<y1<y2<...<yn

#그러므로, i*xi - (x0 + x1 + ... + xi-1) = i*xi - Si-1로 바꿔 계산가능하다.

x_points.sort()
x_sum = x_points[0]
y_points.sort()
y_sum = y_points[0]

for i in range(1,n):

    answer += (x_points[i]*i - x_sum)
    x_sum += x_points[i]  
    answer += (y_points[i]*i - y_sum)
    y_sum += y_points[i]

print(answer)