[BOJ 2399] 거리의 차이

2399번 (거리의 차이)

 

 

이 문제는 단순히 이중 반복문을 이용하여 (x[0] ,x[0]~x[n]) , (x[1], x[0]~x[n]), ... (x[n], x[0]~x[n])

이렇게 총 n^2개의 모든 쌍을 구하는 방식으로 구할 수 있다. 

 

하지만 이 방식은 시간복잡도가 O(n^2)이기 때문에 n이 커지면 시간이 오래 걸리게 되고,

또 이 문제의 분류가 "정렬" 이기 때문에 정렬을 이용하여 문제를 풀어보았다.

 

정렬을 이용한 풀이에는 아주 유용한 "수학적인 아이디어"가 이용된다.

 

1. 우선 정렬을 통해서 n개의 점을 좌표가 오름차순이 되도록 정렬을 한다.

 

2. 특정한 x[i]를 생각해보면, 모든 n^2개의 쌍 중에서, x[i]는 총 2n번 등장하게 된다.

(x[1] ~ x[n] , x[i]) : n개   /   (x[i] , x[1] ~ x[n]) : n개

 

여기서 (x[i], x[i]) 2개를 제외한 총 2n-2번의 등장중에서 x[i]가 몇번 더해지고, 빼는지 구하는게 목표이다.

 

(x[1] ~ x[n] , x[i]) 과 (x[i] , x[1] ~ x[n]) 는 대칭을 이루기 때문에 우선 (x[i] , x[1] ~ x[n]) 에서만 고려를 해보자 - ①

 

정렬이 되었기 때문에 x[i]보다 '왼쪽'에 있는 x[1]~x[i-1]들은 x[i]보다 값이 작다.

반대로 x[i]보다 '오른쪽'에 있는 x[i+1] ~ x[n]들은 x[i]보다 값이 크다.

 

따라서 | x[i] - x[j] | 를 구할 때 j가 1 ~ i-1 의 범위에 있는 경우 | x[i] - x[j] | = x[i] - x[j] 이고,

j가 i+1 ~ n 의 범위에 있는 경우 | x[i] - x[j] | = x[j] - x[i] 가 된다.

 

즉, x[i]를 기준으로, i-1개 (1 ~ i-1) 만큼 x[i]가 더해지고, n-i개 (i+1 ~ n) 만큼 x[i]를 빼주어야 하는 것이다.

 

따라서 ①에 의해서 두번 계산이 되므로 x[i]는 2(i-1)번 더하고, 2(n-i)번 빼야 하므로

전체 합에 ( 2(i-1) - 2(n-i) ) * x[i] 를 더해주면 x[i]에 대해서는 해결이 되는 것이다.

 

그러므로 i=1부터 n까지  ( 2(i-1) - 2(n-i) ) * x[i] 를 모두 더해주면 구하고자 하는 답이 나오게 된다!

 

위 코드는 x[1] ~ x[n] 대신, x[0] ~ x[n-1]로 고려한 것이다.

 

이 방식을 이용하게 되면 정렬을 제외한 부분의 시간복잡도는 O(n)으로,

정렬을 이용하면 더 시간이 짧게 걸리는 것을 알 수 있다.

 

{물론 위의 코드에서는 버블정렬을 이용하였기 때문에 정렬 부분에서 O(n^2)가 되지만, 더 빠른 정렬 알고리즘을 이용하게 되면

단순 이중 반복문보다 더 빠르게 수행될 수 있다.)