<백준 알고리즘> 2399번: 거리의 합

문제

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

즉, 모든 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

---

Solution

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int main(void)
{
	unsigned long long int n, *x=NULL, sum=0;

	scanf("%llu", &n);
	x=(unsigned long long int *)malloc(n*sizeof(unsigned long long int));

	for(int i=0;i<n;i++)
		scanf("%llu", &x[i]);

	for(int i=0;i<n-1;i++)
		for(int j=i+1;j<n;j++)
			sum+=2*abs(x[i]-x[j]);

	printf("%llu\n", sum);

	free(x);
	return 0;
}