[백준 2399] 거리의 합 (C#, C++) - soo:bak

문제 링크

2399번 - 거리의 합

설명

수직선 위에 주어진 여러 점들 간의 모든 거리 차를 합산하는 문제입니다.

입력으로는 n개의 점이 주어지며, 각 점의 위치는 정수입니다.

모든 서로 다른 두 점의 쌍에 대해:

해당 거리의 총합 \(\sum_{i < j} \lvert x_i - x_j \rvert\) 를 두 배로 계산한 값을 출력해야 합니다.
(문제 조건상 \(|x_i - x_j|\) 과 \(\lvert x_j - x_i\rvert\)를 각각 모두 포함시켜야 하기 때문입니다.)

접근법

• 점의 위치를 정렬한 뒤, 누적합을 활용하여 각 위치가 전체 거리합에 기여하는 값을 빠르게 계산할 수 있습니다.
• 또한, 문제의 제약 조건을 확인해보면, 단순한 이중 반복문을 사용해도 시간 제한 내에 충분히 통과할 수 있습니다.
• ‘가장 쉬운 풀이방법’ 으로 풀이하기 위해 이중 반복문을 사용하여 풀이하였습니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    int n = int.Parse(Console.ReadLine());
    var input = Console.ReadLine().Split();
    var arr = Array.ConvertAll(input, int.Parse);

    long sum = 0;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        sum += Math.Abs(arr[i] - arr[j]);
      }
    }

    Console.WriteLine(sum * 2);
  }
}

C++

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vi;

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

  int n; cin >> n;
  vi cord(n);
  for (int& x : cord)
    cin >> x;

  ll ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      ans += abs(cord[i] - cord[j]);
    }
  }

  cout << ans * 2 << "\n";

  return 0;
}