문제
수직선에 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 이하의 정수이다.
출력
첫째 줄에 답을 출력한다.
풀이
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main() {
long *arr;
int num;
long long sum = 0, cnt;
cin >> num;
arr = new long[num];
for (int i = 0; i < num; i++)
cin >> arr[i];
sort(arr, arr + num);
for (int i = 0; i < num; i++) {
cnt = (2 * i - num + 1) * arr[i];
sum += cnt;
}
cout << sum * 2;
}
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
[백준 5052번] 전화번호 목록 / C++ (0) | 2020.08.08 |
---|---|
[백준 2750번] 수 정렬하기 / C++ (0) | 2020.08.06 |
[백준 3047번] ABC / Python (0) | 2020.08.03 |
[백준 2875번] 대회 or 인턴 / C++ (0) | 2020.08.01 |
[백준 1120번] 문자열 / C++ (0) | 2020.07.31 |