[백준 14400번 / java] 편의점 2

문제

14400번: 편의점 2 (acmicpc.net)

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

그 최소 거리의 합을 출력하는 문제.

풀이

고객의 위치가 x, y좌표로 주어졌다.

편의점이 세워질 위치를 모두 탐색하는 방법은 시간 초과를 발생시키므로 옳지 않다.

 

여러 점이 있을 때 그 점들과의 거리의 합을 최소화하는 지점은 정렬된 데이터의 '중간값'이다. 

중간값 위치 기준 왼쪽, 오른쪽 사람 수가 비슷해지는데, 이때 어느 한쪽으로 위치를 이동시키더라도 전체 거리의 합이 증가할 수밖에 없으므로 중간값이 최적의 값이 된다.

 

답을 평균값으로 생각하기 쉬운데, 거리에 관한 문제라서 평균값은 오히려 거리를 증가시킬 수 있다. 

 

1차원으로 예시를 들면 위치 2, 5, 20에 사람이 있다고 가정하자.

평균값 9 : 7+4+11=22

중간값 5 : 3+0+15=18

평균값은 사람이 없는 위치에 편의점을 세우게 하므로 오히려 전체 거리의 합이 증가한다.

코드

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

public class boj_14400 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        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);

        //편의점 위치
        int midX = x[N/2];
        int midY = y[N/2];

        long distX = 0;
        long distY = 0;

        for(int i=0; i<N; i++){
            distX += Math.abs(midX - x[i]);
            distY += Math.abs(midY - y[i]);
        }

        long sum = distX + distY;
        System.out.print(sum);
    }
}