본문 바로가기
알고리즘/백준

[백준 23330] 거리의 합 2 (C++)

by fortissimo 2024. 7. 1.

https://www.acmicpc.net/problem/23330

문제


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

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

입력


 

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

 

출력


첫째 줄에 답을 출력한다.

 

문제 풀이


정렬 문제.

오름차순 정렬한 후 첫번째 원소에 대해 다른 모든 원소와의 거리의 합을 구한다. 이를 prevSums라고 하자. 나머지 원소는 이전 원소와의 거리의 합인 prevSums와 각 원소의 위치에 영향을 받는다. 예시 1을 통해 설명한다.

첫번째 원소와 모든 원소와의 거리의 합은 10이다.

 

두번째 원소와 모든 원소와의 거리의 합은 7인데, 이를 자세히 보면 이미 계산을 마친 첫번째 원소는 거리가 0에서 1로 증가하였고, 나머지 원소들은 거리가 각각 1에서 0으로, 2에서 1로, 3에서 2로, 4에서 3으로 감소하였다. 계산을 마친 첫번째 원소는 거리를 구할 때 첫번째 원소와 두번째 원소 사이의 거리만큼 이전보다 멀어졌기 때문이고, 나머지는 첫번째 원소와 두번째 원소 사이의 거리만큼 전보다 가까워졌기 때문이다. 따라서 이전 계산 값인 10에 +1 - 4인 7이 거리의 합이 된다. 

 

세번째 원소와 모든 원소와의 거리의 합은 6인데, 이 역시 이미 계산을 마친 첫번째 원소와 두번째 원소는 거리가 1씩 증가하였고, 나머지 원소들은 거리가 1씩 감소하였다. 따라서 이전 계산 값인 7에 +2 - 3인 6이 거리의 합이다.

 

네번째 원소는 3번째 원소까지 1씩 증가하고 4~5번째 원소는 1씩 감소하여 거리의 합이 7이 되었다.

 

네번째 원소는 4번째 원소까지 1씩 증가하고 5번째 원소는 1씩 감소하여 거리의 합이 10이 되었다.

 

 

위의 예시를 통해 이전 원소와 다른 원소들까지 거리의 합에 i(=해당 인덱스 이전까지의 원소의 개수)와  (i번째 원소와 i-1번째 원소 사이의 거리)을 곱해준 값을 더해주고, N-i(나머지 원소의 개수)와 (i번째 원소와 i-1번째 원소 사이의 거리)을 곱한만큼 빼주면 i번째 인덱스의 원소와 다른 원소들 사이의 거리의 합을 구할 수 있다.

 

아래는 코드.

더보기
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int* arr = new int[N];
	long long answer = 0;
	long long prevSums = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	for (int i = 0; i < N; i++)
	{
		prevSums += abs(arr[i] - arr[0]);
	}
	answer += prevSums;
	for (int i = 1; i < N; i++)
	{
		long long diff = arr[i] - arr[i - 1];
		answer += prevSums + (diff * i) - (diff * (N - i));
		prevSums = prevSums + (diff * i) - (diff * (N - i));
	}
	cout << answer << "\n";
	return 0;
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준 1735] 분수 합 (C++)  (0) 2024.07.03
[백준 7562] 나이트의 이동 (C++)  (0) 2024.07.02
[백준 9342] 염색체 (C++)  (0) 2024.06.30
[백준 1051] 숫자 정사각형 (C++)  (0) 2024.06.29
[백준 17251] 힘 겨루기 (C++)  (0) 2024.06.28