BOJ 2399 - 거리의 합

문제

N개의 수가 주어졌을 때, 모든 순서쌍 (i, j)에 대해 |a_i - a_j|의 합을 구하라 (i=j 포함).

입력

첫째 줄에 N, 둘째 줄에 N개의 수가 주어진다.

출력

모든 쌍의 차이 절댓값 합을 출력한다.

예제

입력	출력
`3` `1 3 5`	`16`

풀이

이중 반복문으로 모든 순서쌍을 순회하며 차이의 절댓값을 합산한다.

N개의 수를 배열에 저장한다
모든 (i, j) 쌍에 대해 abs(a[i] - a[j])를 누적한다
값이 커질 수 있으므로 long long 타입을 사용한다
최종 합을 출력한다

핵심 아이디어: 순서쌍 (i, j)와 (j, i)를 모두 포함하므로 이중 반복문으로 O(N^2)에 직접 계산한다.

코드

#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
int n;
ll map[10100];
int main()
{
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    scanf("%lld", &map[i]);
  }
  ll ans = 0;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      ans += abs(map[i] - map[j]);
    }
  }
  cout << ans << endl;
}

복잡도

시간: O(N^2)
공간: O(N)

문제