백준 알고리즘] 2399 - 거리의 차이

시간 제한 : 2초

메모리 제한 : 128MB

문제

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
	int n;
	long long *list, sum = 0;
	cin >> n;
	list = new long long[n];
	for (int i = 0; i < n; i++)
		cin >> list[i];
	sort(list, list + n);
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			sum += list[j] - list[i];
	cout << sum * 2;
}

Tip

정렬해주고 그 상태에 대해서 차이 값을 전부 더하면 된다. x[i]-x[j]와, x[j]-x[i]를 다르게 취급하므로, 한 번만 계산해주고 2를 곱한 값만 출력해내면 끝이다. 정렬이라는 것만 고려하면 어렵지 않은 문제.