[백준 2399] 거리의 합(수정예정)

문제출처: https://www.acmicpc.net/problem/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 이하의 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이

이 문제로 효율적인 시간복잡도를 갖는 알고리즘의 설계의 중요성을 알 수 있습니다. 이 문제를 각각 O(n^2), 0(n^2/2), O(nlogn)으로 풀 수 있는데 엄밀히말해서 입력값이 1만이므로 최악의 경우 1억번의 연산을 해야하므로 O(nlogn)으로 풀어야만합니다. 하지만 이 문제는 O(n^2)의 연산풀이도 정답이되는것 같습니다.

O(n^2) : 입력한 수들을 모두 각각 비교하면서 총합을 구합니다. 쓸모없는 연산을 하는 단점이있습니다.(1,2,3,4,5일때 (1.1),(2,2),(3,3),(4,4),(5,5) )

O(n^2/2) : O(n^2)의 방식에서 언급한 쓸모없는연산(본인과 본인사이의 거리)을 하지않고 , 두번더하는연산((1,2),(2,1),(4,5),(5,4)...)을 한번으로줄입니다. 구해진 ans*2가 답입니다. 

O(n^2)의 방식은 n이 5일때 총 5*5=25번연산, O(n^2/2)의 방식은 입력값끼리 한번씩만 연산하므로(O(n^2)의 절반만 계산) 약 O(n^2/2)입니다.

그런데 시간복잡도 상 O(n^2)와 O(n^2/2)는 둘다 O(n^2)로, 여전히 시간초과가 날 우려가 있습니다.

더 좋은방법은 없을까요? 바로 O(nlogn)방법이있습니다. 

10,1,3,7 이있다고칠때, 가장 작은값부터 오름차순으로 좌표값의차이를 비교해가며  연산을 하기위해 1,3,7,10으로 정렬합니다.

(정렬하지않으면 연산식을 같게해도 답이다릅니다. ex) 10,3,1,7-> 94, 1,7,10,3-> 102

사실상 정렬하지않고 연산한 방식을 

여기서, 규칙을 발견할 수 있습니다. 1과 3의 간격 2, 1과 7 의 간격 6, 1과 10의 간격 9, 3과 7의 간격 4, 3과 10의간격 7, 7과 10의 간격3, 이값들을 모두더하고 *2를하면 그게답입니다. 즉,  1,3,7,10일 때 1에서 모든숫자간의 간격 + 3에서 남은 모든숫자의간격(1제외)+ 7과 남은 모든숫자의간격을 구하는겁니다.

여기서 O(n^2/2)와 O(nlogn)의 연산의 차이는 후자의 경우 각 숫자의 간격을 단 한번만 구하고 그 값이 간격을 계산할 때 나오는 경우만큼 곱해주는것입니다.

전자의 경우 10,1,3,7 일때 (1,2),(1,3),(1,4),(2,3),(2,4),(3,4)의 간격을구하죠. 그러나 후자는 3->3->1번씩 구하는게아니라 1->1->1번씩구하고 그 간격의 값들을 곱해주고 더해나갑니다. 위의 예로는 (1.2),(2,3),(3,4) 이렇게 딱 3번만연산합니다. 반복문으로 구해지는 i번째의 인덱스일때 간격 6=(1,3)+(3,7), 16=(1,10)+(3,10), 9=(1,7)+(7,10))

결론적으로 n이4일때 각 시간복잡도의 연산횟수는 16, 6, 3 이렇게되겠습니다.

코드

0~21행: O(nlogn), 38행(n^2/2), 37행(n^2)

#pragma warning(disable:4996)
#include<iostream>
#include<algorithm>
using namespace std;
int arr[10001];
int main()
{
	int n;
	scanf("%d", &n);
	long long ans = 0;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	sort(arr, arr + n);
	for (int i = 1; i < n; i++)
	{
		ans += (arr[i] - arr[i - 1]) * i * (n - i);
	}
	printf("%lld\n", ans * 2);
}

//#include<iostream>
//using namespace std;
//int arr[10001];
//int main()
//{
//	int n;
//	cin >> n;
//	long long ans = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> arr[i];
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = i + 1; j <= n; j++)
//		for(int j=1;j<=n;j++)///////
//		{
//			ans += abs(arr[i] - arr[j]);
//		}
//	}
//	cout << ans * 2 << endl;
//}

결과