[정렬] 백준 2399 :: 거리의 합

거리의 합 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	1628	807	642	52.110%

문제

수직선에 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

 

   

 문제 풀이

처음 봤을 땐, 정렬문제가 맞을까 의심했던 문제.

수학이 이렇게 중요합니다 여러분,

1차 풀이 (  1988 KB,  48 ms)

• 무식하게 두 요소의 차이를 구한 뒤, 절대값을 씌우고 누적합에 더한다.
  
• 정렬 필요 없음.
• 시간 복잡도 (n제곱).

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        int32_t N;
        int64_t sum = 0, dist;
        cin >> N;
        int32_t data[N];
        for(int i=0; i<N; i++) cin >> data[i];
        for(int i=0; i<N; i++){
                for(int j=i+1; j<N; j++){
                        dist = data[i] - data[j];
                        if(dist < 0) dist *= -1;
                        sum += dist;
                }
        }
        cout << sum*2;
}

2차 풀이 (  1988 KB,  0 ms)

• 이번에는 정렬을 이용하여 빠르게 풀어보자.
• 배열을 오름차순으로 정렬하고, 더해지는 팩터가 무엇인지 펼쳐본다.
  색칠한 부분은 중복이거나, 0인 팩터.

• 따라서,  a[i] * ( 2i - n + 1 ) 만큼 결과에 더해진다.  // 계산시, 오버플로우에 주의.
• 각 i에 대해 순회하면서 더해주고,  출력하기 직전에 2를 곱해주면 끝.
• 선형 시간 복잡도.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        int32_t N;
        cin >> N;
        int64_t data[N];
        int64_t sum = 0;
        for(int i=0; i<N; i++) cin >> data[i];
        sort(data, data+N);

        for(int i=0; i<N; i++) {
                sum += data[i] * ( 2 * i - N + 1 );
        }
        cout << sum * 2;
}