Baekjoon 2399 거리의 합 JAVA

2399번: 거리의 합

문제

수직선에 n개의 점이 찍혀 있다. 각각의 점의 x좌표가 주어졌을 때, n2개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하시오.

즉, 모든 i, j에 대해서 |x[i] - x[j]|의 합을 구하는 것이다.

입력

첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 x[1], x[2], x[3], …, x[n]이 주어진다. 각각은 0 이상 1,000,000,000 이하의 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이

이중 for문을 이용하여 모든 쌍에 대한 거리의 차를 구해서 더한다.

이렇게 되면 A -> B로 가는 모든 값을 구할 수 있다.

문제에서는 모든 i, j에 대해서 x[i] - x[j]의 합을 구하는 것이 조건이기에

B -> A 가는 거리의 합도 찾아야 하기에 A -> B로 가는 거리의 합에 * 2를 하여 B -> A로 가는 거리의 합도 구한다.

코드

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		long ans=0;
		int [] x=new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++)
			x[i]=Integer.parseInt(st.nextToken());
		for(int i=0;i<n;i++)
			for(int j=i+1;j<n;j++)
				ans+=Math.abs(x[i]-x[j]);
		System.out.println(ans*2);
	}
}