[백준] 2399번: 거리의 합

ㅂhttps://www.acmicpc.net/problem/2399

2399번: 거리의 합

코드

import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[] x = new int[N];
		long allDistance = 0;	// 모든 쌍의 거리를 더한 값
		
		for(int i=0; i<N; i++) 
			x[i] = scan.nextInt();
		
		for(int i=0; i<x.length; i++) 
			for(int j=0; j<x.length; j++) 
				allDistance += Math.abs(x[i]-x[j]);
		
		System.out.println(allDistance);
		scan.close();
	}

}

 

풀이

문제만 이해하면 쉽게 해결 할 수 있다.

n^2개의 모든 쌍에 대해서 거리를 더한 값이므로.

x의 좌표가 1 5 3 2 4 일때,

처음부터 모든 수를 반복하며 거리를 구해서 더해주면 된다.

x의 좌표가 1일때...

1 ~ 5의 거리 : 4

1 ~ 3의 거리 : 2

1 ~ 2의 거리 : 1

1 ~ 4의 거리 : 3

4+2+1+3 = 10

 

위와 같이 모든 좌표에 대해 다른 좌표들과의 거리를 구해서 더해준다.

문제에서 x 좌표의 범위가 0 이상 1,000,000,000 이므로,

모든 쌍의 거리를 더한 값은 int가 아닌 long 으로 선언해줘야 한다.