[백준] 2399번 풀이 _ 거리의 합

1. 문제

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

2. 풀이 방법

2.1. $ O(N^2) $ 풀이

보자마자 떠오르는 생각. 직접 하나하나씩 비교해서 값을 구합니다.
c언어의 경우에 통과할 수 있지만, python은 이렇게 해도 시간초과가 발생합니다.

2.2. $ O(N) $ 풀이

모든 구해야 하는 값을 위의 그림처럼 표로 나열해봅니다. 그러면 앞에 있는 [i] 의 개수는 $ i $개, 뒤에 있는 -[i] 개수는 $ n - i - 1 $ 개가 나오게 됩니다. 두 수의 합은 $ i * i + -i * (n - i - 1) = i * i + i * (-n + i + 1) = i * (2i + 1 - n) $ 이 나오게 됩니다. 즉, 값에서 사용되는 i 의 개수는 $ 2i + 1 - n $ 개입니다.

각 수에 대하여 위의 계산을 모두 적용해주면 답을 구할 수 있습니다.

3. 소스코드

3.1. python 시간 초과 $ O(N^2) $ 코드

from sys import stdin 
sum = 0
N = int(stdin.readline())
x_list = list(map(int, stdin.readline().split()))
for i, x in enumerate(x_list):
  for y in x_list[i+1:]:
    sum += abs(x - y)
print(sum*2)

3.2. c로 해결한 $ O(N) $ 풀이

#include<iostream>
#include<algorithm>
using namespace std;
long long arr[10001];
int main()
{
	int n;
	scanf("%d", &n);
	long long ans = 0;
	for (int i = 0; i < n; i++) scanf("%lld", &arr[i]);
	sort(arr, arr + n);
	for (int i = 0; i < n; i++) ans += arr[i] * ( 2 * i - n + 1 );
	printf("%lld\n", ans * 2);
}