거리의 합

문제

백준 2399번 - 거리의 합

언어

JavaScript

순서도

오름차순으로 정렬 후 BigInt 형으로 변환
2 차원 행렬로 표현했을 시 규칙에 맞게 대각선 아래 부분의 합 구하기
구한 합을 두배로 만든 후 반환

문제 풀이 step 1

수직선에 n 개의 점이 찍혀있습니다.
각각의 점의 x 좌표가 주어졌을 때, n ^ 2 개의 모든 쌍에 대해서 거리를 더한 값을 구하는 문제입니다.
즉, 모든 i, j 에 대해서 |x[i] - x[j]| 의 합을 구하는 것입니다.

문제 풀이 step 2

문제는 상당히 간단합니다. 그냥 모든 i, j 쌍에 대해서 거리 차이를 구하면 됩니다.
이는 2 중 반복문을 통해서 구현할 수 있습니다.
- 하지만, 수의 범위가 크기 때문에 Number 형으로 할 경우, 오버플로우가 발생합니다.
- 이를 해결하기 위해서 BigInt 형으로 변환 후 2 중 반복문으로 구현해봤지만, 이러면 시간초과가 발생합니다.
- 아무래도 BigInt 형의 연산이 더 오래 걸리기 때문인 것 같습니다.
속도를 더 빠르게 하기 위해서 행렬의 대각선 아래 부분만 구하고 2 를 곱해줍니다.
- 모든 i, j 쌍에 대해서 거리차를 구해서 행렬 형태로 나타내면, 대각선 기준으로 아래와 위가 동일합니다.
- 따라서 대각선 아래 부분만 구하고 2 를 곱해주면 됩니다.
- 하지만 이렇게 해도 BigInt 형의 연산이 오래 걸리는지 시간초과가 발생합니다.
정렬한 행렬에서 규칙을 찾고, 규칙에 맞게 행렬의 대각선 아래 부분만 구하고 2 를 곱해줍니다.
- 사진을 보면 규칙이 눈에 보이실 것입니다.
- 파란색 사각형으로 표시된 부분을 보면, 1 개에서 시작해서 매 단계마다 한 개씩 늘어나고 있습니다.
- 빨간색으로 표시된 부분을 보면, n - 1 개에서 시작해서 매 단계마다 한 개씩 줄어들고 있습니다.
- 이렇게 찾은 규칙을 식으로 나타내면, sum += x[k] * k - x[k - 1] * (n - k) 와 같습니다.
- 위의 식을 1 ~ n 까지 반복해서 대각선 아래 부분의 합을 구하고 그 합에 곱하기 2 를 해주면 됩니다.
- 이 경우는 무리 없이 시간 안에 해답이 구해집니다.
추가 설명은 주석으로 작성하겠습니다.

후기

매번 느끼지만, 수학 문제의 경우는 해답을 빠르게 찾기 위한 규칙이 있는 경우가 많고, 그 규칙을 찾는 가장 쉬운 방법은 하나씩 나열해보는 것입니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const n = Number(input[0]);
	// 오름차순으로 정렬
	const arr = input[1]
		.split(" ")
		.map(Number)
		.sort((a, b) => a - b)
		.map(BigInt);

	// 규칙에 맞게 대각선 아래 부분의 합 구하기
	let res = 0n;
	for (let i = 1; i < n; i++) {
		res += arr[i] * BigInt(i) - arr[i - 1] * BigInt(n - i);
	}

	// 2 를 곱하고 반환하기
	return (2n * res).toString();
};

console.log(solution(input));