[BOJ/백준] 2399번 : 거리의 합 (Java)

2399번 : 거리의 합 (https://www.acmicpc.net/problem/2399)

---

문제

---

접근 방법

---

• 좌표들이 수직선 위에 있으므로 하나의 좌표 쌍의 거리는 여러 좌표 쌍의 거리의 합과 같다. _a와 c의 사이 거리 = a와 b 사이의 거리 + b와 c 사이의 거리*
• 따라서 모든 쌍에 대해서 거리의 합을 구하기 위해 접한 좌표들 사이의 거리가 각각 몇 번씩 더해지는지를 구한다.

• 문제에서는 n개의 점이 있을 때 n 제곱 개의 쌍이 있다고 했으므로 (a,b) 조합과 (b,a)의 조합은 다른 것이다. 따라서 모든 조합에 대한 거리의 합을 구한 후 2를 곱하여 출력한다.

• 인접한 좌표들 사이의 거리가 각각 몇 번씩 더해지는지에 대한 식을 세우기 위해 다음 예시를 보자. _n=6일 때의 예시* 위의 예시를 보면 모든 조합의 거리의 합에서 인접한 좌표들의 거리가 각각 몇 번 더해졌는지 보면 (n-i) \* i (i = 1, 2, ..., n-1)번 더해진 것을 볼 수 있다.

• 따라서
  1. 입력받은 좌표를 정렬한 후 (n의 범위가 1,000이므로 정렬 가능)
  2. 인접한 좌표 사이의 거리를 구하고
  3. 각각의 거리가 더해진 횟수만큼 곱한 값을 전부 더한 값에
  4. 2를 곱하여 출력한다.

• 주의할 점
  • 인접한 좌표 사이의 거리는 최대 1,000,000,000이므로 long을 사용한다.

코드

---

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int x[] = new int[N];
		for (int i = 0; i < N; i++) {
			x[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(x);
		long diff[] = new long[N];
		for (int i = N - 1; i > 0; i--) {
			diff[i] = x[i] - x[i - 1];
		}
		int end = N / 2;
		long sum = 0;
		for (int i = 1; i <= end; i++) {
			sum += (diff[i] + diff[N - i]) * (N - i) * i;
		}
		if (N % 2 == 0) {
			sum -= diff[end] * (N - end) * end;
		}
		bw.write(String.valueOf(sum * 2));
		bw.flush();
		bw.close();
		br.close();
	}
}

위의 코드의 성능

정리

---

모든 조합의 거리를 전부 구하게 되면 시간이 늘어나므로 한 쌍의 거리를 여러 쌍의 거리로 나눌 수 있다는 아이디어가 시간을 줄이기 위한 포인트이다.