백준 2399 거리의 차이

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 각 인덱스에서 다른 모든 인덱스와의 차이의 합들을 모두 구하는 문제입니다.

 

입력이 10000개이고 시간 제한이 1초라서 O(N^2)은 뭔가 애매할거 같아서 저는 0번째 인덱스부터 가면서 나오는 수들의 절댓값을 2배씩하면서 앞으로 진행 하였습니다. 이런식으로 하면 처음에는 n-1번의 연산을 하고 이후에 한번씩 줄어 마지막에 1번만 연산을 하면 되므로 각 인덱스를 n-1번씩  해주는 방법보다 효율적이라고 할 수 있습니다.

 

아래는 코드입니다.

 

#include <iostream>
#include <cmath>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n;
	cin >> n;
	int arr[n];
	long long sum = 0;
	
	for(int i = 0; i < n; i++)
		cin >> arr[i]; 
	
	for(int i = 0; i < n-1; i++)
		for(int j = i+1; j < n; j++) 
			sum+=2*abs(arr[i]-arr[j]);
	
	cout<<sum;
	return 0;	 
}