2399번-거리의 합

거리의 합

시간 제한	메모리 제한
1 초	128 MB

문제

수직선에 n개의 점이 찍혀 있다. 각각의 점의 x좌표가 주어졌을 때, n²개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하시오.

즉, 모든 i, j에 대해서 |x[i] - x[j]|의 합을 구하는 것이다.

입력

첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 x[1], x[2], x[3], …, x[n]이 주어진다. 각각은 0 이상 1,000,000,000 이하의 정수이다.

출력

첫째 줄에 답을 출력한다.

예제

예제 입력 1

5
1 5 3 2 4

예제 출력 1

40

나이브하게 풀면 이렇습니다.

n,*a=map(int,open(0).read().split())
t=0
for i in range(n-1):
    for j in range(i+1,n):
        t+=abs(a[i]-a[j])
print(t<<1)

하지만 n의 크기가 크기 때문에 불가능합니다.

🎯 목표

우리는 다음 식의 값을 빠르게 구하고 싶습니다:

$$ \sum_{0 \le i < j < n} |a[i] - a[j]| $$

단, 시간 초과를 피하기 위해 절댓값 합을 수학적으로 효율적으로 계산하려고 합니다.

🧩 1단계: 정렬을 가정

정렬된 배열 a = [a_0, a_1, ..., a_{n-1}]는 다음과 같은 특징을 가집니다:

• i < j일 때 항상 a[i] ≤ a[j]
• 즉, 절댓값 없이도 $$ |a[i] - a[j]| = a[j] - a[i] $$

따라서 다음과 같이 쓸 수 있습니다:

$$ \sum_{0 \le i < j < n} |a[i] - a[j]| = \sum_{0 \le i < j < n} (a[j] - a[i]) $$

🧩 2단계: 괄호를 분리해서 합을 나눠보기

우변을 다음처럼 분리합니다:

$$ \sum_{0 \le i < j < n} (a[j] - a[i]) = \sum_{0 \le i < j < n} a[j] - \sum_{0 \le i < j < n} a[i] $$

🧮 3단계: 각 원소 a[k]가 몇 번 등장하는가?

• 🔹 a[k]가 오른쪽 항(a[j])으로 등장할 경우예시로 확인
  • k = 2 (a[2] = 6)이라면,
    • (i,j) = (0,2), (1,2) 두 번 등장 → 2번

  ---

  🔹 a[k]가 왼쪽 항(a[i])으로 등장할 경우예시로 확인
  • k = 0 (a[0] = 1)이라면,
    • (i,j) = (0,1), (0,2) → 2번
  • 총 n=3이니까: 3 - 1 - 0 = 2번 등장
• 즉, a[k] = a[i]일 때, 가능한 j는 j > i = k입니다.
  → 그러면 j = k+1, k+2, ..., n-1까지 될 수 있어요.
  → 총 개수는 n - 1 - k번입니다.
• 즉, a[k] = a[j]일 때, 가능한 i는 i < j = k입니다.
  → 그러면 i는 0, 1, ..., k-1까지 될 수 있죠.
  → a[k]는 오른쪽 항에서 총 k번 등장합니다.

🧮 4단계: a[k]의 최종 기여

각 a[k]는 오른쪽에서는 +a[k]로 k번, 왼쪽에서는 -a[k]로 (n−1−k)번 등장하므로:

$$ \text{기여도}(a[k]) = a[k] \cdot \left(k - (n - 1 - k)\right) = a[k] \cdot (2k - n + 1) $$

✅ 결론: 계수 도출 완료!

$$ \text{기여도}(a[k]) = a[k] \cdot (2k - n + 1) $$

이걸 전 원소에 대해 모두 합하면:

$$ \sum_{k=0}^{n-1} a[k] \cdot (2k - n + 1) $$

n, *a = map(int, open(0).read().split())
a.sort()
t = 0
for i in range(n):
    t += (2*i - n + 1) * a[i]
print(t * 2)

 

💡 마지막으로 출력은 왜 ×2?

문제는 원래:

$$ \sum_{0 \le i < j < n} |a[i] - a[j]| + \sum_{0 \le j < i < n} |a[j] - a[i]| = 2 \cdot \sum_{0 \le i < j < n} |a[i] - a[j]| $$

대칭 쌍을 고려해서 결과를 2배 해줍니다.

✨ 전체 정리

단계	설명
정렬	절댓값 없이도 a[j] - a[i]로 변환 가능
식 분리	a[j] 합 - a[i] 합으로 나눔
각 원소 기여도 분석	오른쪽 등장 횟수: k번 왼쪽 등장 횟수: n−1−k번
기여도 계수	2k - n + 1
결과 식	sum(a[k] * (2k - n + 1)) * 2

이 과정을 바탕으로, 시간이 많이 걸리는 O(n^2) 계산을
정렬 + 한 번의 합산으로 O(n log n) 안에 끝낼 수 있습니다.