백준 23330 : 거리의 합 2

문제 설명

---

수직선에 n개의 점이 주어졌을 때,  n * n개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하는 문제.

---

 

주어진 문제의 답을 구하기 위해선 모든 요소간의 차이의 2배를 출력하면 된다.

예를 들어

5

1 2 3 4 5

와 같은 입력예가 있을 때, (1, 5)한번 (5, 1)한번으로 총 두번 계산되기 때문이다.

 

그렇다면 모든 요소간의 차이는 어떻게 구할까?

먼저 주어진 배열을 정렬한다.(정렬이 안된상태로 주어진다.)

오름차순 정렬이 되었다면, 현재 탐색중인 요소 전에는 현재의 요소보다 작은 수 밖에없다.

예를 들어

5

1 2 3 4 5

와 같은 예시에서 5 이전에는 1, 2, 3, 4로, 5보다 작은 수 밖에 없다. 이를통해 5와 다른 수들의 차를 구할 수 있다.

(5 - 4) + (5 - 3) + (5 - 2) + (5 - 1) = (5 * 4) - (1 + 2 + 3 + 4)

즉 현재값의 바로전값까지의 누적합을 (현재값) * (현재 idx - 1)에 빼준값이 모든요소간의 차이가 되는 것이다.

---

소스 코드

#include <stdio.h>
#include <algorithm>

using namespace std;

int n;
long long arr[500010];
long long sum[500010];

int main()
{
    int i, j;
    scanf("%d", &n);
    for(i=1;i<=n;i++) {
        scanf("%lld", &arr[i]);
    }
    sort(arr + 1, arr + n + 1);
    for(i=1;i<=n;i++) {
        sum[i] = sum[i - 1] + arr[i];
    }
    long long ans = 0;
    for(i=2;i<=n;i++) {
        //printf("%lld %d %ld\n", arr[i], i - 1, sum[i-1]);
        ans += ((arr[i] * (i-1)) - sum[i-1]);
    }
    printf("%lld", ans * 2);
    return 0;
}

자료형에 주의하자. ans와 누적합은 int에 다 담기지 않는다.