[boj14400/Java]편의점 2

https://www.acmicpc.net/problem/14400

14400번: 편의점 2

이 문제에서 고려해야하는 것은 거리의 계산을 유클리드 거리(대각선 길이 = 제곱을 이용)를 이용하는 것이 아니라 

멘하튼 거리(좌표 차의 합)을 이용하고 있다는 점이다. 

문제를 해결함에 있어 처음에는 평균을 이용해야하는건지 고민이 있었는데,

일단 거리 최솟값을 구할 때 x좌표랑 y좌표를 따로 생각해서 x좌표끼리, y좌표끼리 최소가 되는 점을 정하면 될 것이라고 생각했다. 그렇다면 x좌표들 중에서 거리의 합이 최소가 되도록하는 x좌표는 어떻게 구할 수 있을까?

자료도 찾아보고 친구들이랑 얘기해보면서 평균을 이용하는 경우

x 좌표 기준으로 1 2 3 100 이렇게 4개의 좌표가 있다면 100때문에 3을 최소로 했을 때보다 거리의 합이 크게 된다.

그렇기 때문에 일단 평균은 답을 구하는 방법에서 제외해야 한다.

 

그렇다면 최소 값을 어떻게 구할 수 있을까?

 

적은 수의 좌표에서부터 생각해보자. 

먼저 2개의 좌표가 있는 경우 사실 두 좌표 사이의 어느 점을 골라도 최솟값은 두 점 사이의 거리로 일정하다.

심지어 두 좌표 중 하나를 골라도 최솟값은 두 점 사이의 거리이다.

3개의 좌표가 있는 경우는 좌표를 정렬해서 나열했을 때

1 3 5 이렇게 좌표가 있다면 1~5 안에서 좌표를 고른다면 고른 좌표로부터 1과 5가 떨어져 있는 거리는

항상 일치한다. 그렇기 때문에 정렬 시 중앙값인 3을 골라야 거리의 합이 최소가 될 수 있다.

이를 일반화 시켜서 생각해보면 항상 정렬 시 중앙값을 골랐을 때가 거리의 합이 최소가 된다는 것을 알 수 있다.

 

사실 해답을 떠올리기가 어렵지 구현자체는 어렵지 않았음

코드는 다음과 같다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int xMid=0, yMid=0;
		int N = Integer.parseInt(st.nextToken());
		int[] x = new int[N];
		int[] y = new int[N];
		for(int i = 0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			x[i] = Integer.parseInt(st.nextToken());
			y[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(x);
		Arrays.sort(y);
		
		xMid = x[N/2];
		yMid = y[N/2];
		
		long dist = 0;
		for(int i = 0; i<N; i++) {
			dist += Math.abs(xMid - x[i]);
			dist += Math.abs(yMid - y[i]);
		}
		
		System.out.println(dist);
	}

}