[백준] 14400번 편의점 2 자바 풀이

문제

시간 제한메모리 제한제출정답맞힌 사람정답 비율

 

2 초

512 MB

1081

460

346

41.587%

문제

영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고객들이 어느 위치에 존재하는지 파악을 하였고, 모든 고객들의 거리의 합을 최소로 하려한다. 두 위치의 거리는 |x1-x2|+|y1-y2|로 정의한다.

n명의 주요 고객들의 위치 (xi,yi)이 주어질 때, 모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 세울 때, 그 최소 거리 합을 출력하시오.

입력

첫째 줄에는 주요 고객들의 수n이 주어진다.(1≤n≤100,000)

다음 n줄에는 고객들의 위치 (x,y)가 주어진다.(-1,000,000≤x,y≤1,000,000)

출력

모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 세울 때, 그 최소 거리 합을 출력하시오.

풀이

맨해튼 거리란 유클리드 거리와 함께 좌표간의 거리를 구하는 방식을 말하는데, 아래의 그림을 봤을 때 빨간색, 파란색, 노란색은 모두 12로 가장 짧은 맨하탄 거리이다. 초록색으로 직선 거리를 표현 한 것이 유클리드 거리이다.

출처 : 위키백과

위 문제에서 두 위치의 거리를 |x1-x2| + |y1-y2|로 표현 했으므로, 이 문제는 최소 맨해튼 거리의 합을 구하는 문제이다.

가장 짧은 거리를 구한다고 했을 때, 먼저 떠오르는 방법은 입력받은 가장 작은 좌표와 가장 큰 좌표의 중간 값이라고 생각했다.

좌표의 맨해튼 거리의 합이 최소가 되는 지점이 될 만한 부분은 두가지가 있었다.

1. x,y 좌표 각각의 중간 인덱스
2. x,y 좌표 각각의 합을 좌표의 갯수로 나눈 점

결론적으로 x,y 좌표 각각의 중간 인덱스가 올바른 최소값 이었고, 문제를 나같은 멍청대가리에게도 쉽게 설명해준 Hi군에게 감사 인사를 전한다.

아주 간단하게 1차원 좌표에서 확인 해보면, 5개의 점이 있다고 치자.

0 10 20 30 100 다섯개의 점에서 맨해튼 거리의 합이 최소가 되는 지점은 어디일까

1번 방법으로 값을 구한다면 5 / 2 = 2 로 2번 인덱스인 20이 중간 지점이 될 것이고,

2번 방법으로 값을 구한다면 0 + 10 + 20 + 30 + 100 / 5 로 32가 중간지점이 될 것이다.

그렇다면 이 중간지점을 토대로 각 좌표들의 거리의 합을 구하면 어떻게 될까

1번 방법은 20 + 10 + 0 + 10 + 80 으로 120

2번 방법은 32 + 22 + 12 + 2 + 68 으로 136이라는 값이 나온다.

x,y 좌표 각각의 중간 인덱스를 구한 후 |x1-x2| + |y1-y2| 계산하는 코드를 그대로 옮겨서 풀었다.

코드

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 IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 이거오류
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        long answer = 0;
        int[][] arr = new int[N][2];
        int[] x = new int[N];
        int[] y = new int[N];

        for (int i = 0; i < N; i++) {
            String[] s = br.readLine().split(" ");
            x[i] = Integer.parseInt(s[0]);
            y[i] = Integer.parseInt(s[1]);
            arr[i][0] = x[i];
            arr[i][1] = y[i];
        }
        Arrays.sort(x);
        Arrays.sort(y);
        int compX = x[N/2];
        int compY = y[N/2];
        for (int i = 0; i < N; i++) {
            answer += Math.abs(arr[i][0] - compX) + Math.abs(arr[i][1] - compY);
        }
        System.out.println(answer);
    }
}