BOJ 2399. 거리의 합

https://www.acmicpc.net/problem/2399이 문제를 해결하는 데는 크게 세 가지 방법이 있다.1. O(N^2)의 시간에 해결하는 방법.2. O(N^2 / 2)의 시간에 해결하는 방법.3. O(N)의 시간에 해결하는 방법. 정렬 후 배열이 a_0, a_1, ..., a_n-1이 되었다고 합시다. 각 n^2개의 쌍 중, a_i는 (a_0 ~ a_n, a_i)와 (a_i, a_0~a_n)로 총 2*n번 등장합니다. 여기서 a_i의 상대를 a_j라고 하면, a_i > a_j일 때는 a_i - a_j로 계산할테니 a_i는 답에서 더해질테고, 반대면 빼질것입니다. a_i,a_i 두개를 제외하고 총 2*n-2개의 쌍에서 a_i보다 큰 원소와 작은 원소가 각각 몇개인지 세봅시다. a_i보다 큰 원소는 a_i+1 ~ a_n-1까지 총 (n-1)-(i+1)+1..........

원문링크 : BOJ 2399. 거리의 합