14400번. 편의점 2

 

아이디어

고객들의 위치를 (a1, b1), (a2, b2), ... (an, bn) 이라고 하고 편의점의 위치를 (x, y) 라고 할 때 모든 고개들의 거리 합은 다음과 같이 정의할 수 있다.

 

|x - a1| + |x - a2| + ... + |x - an| + |y - b1| + |y - b2| + ... + |y - bn|

 

|x - a1| + ... + |x - an| 과 |y - b1| + ... |y - bn| 을 각각 x 에 대한 함수, y 에 대한 함수로 바라볼 때 각각의 함수는 기울기가 음에서 0 또는 양으로 바뀌는 변곡점을 가지게 되고 이 때의 값이 가장 거리합을 최소화 할 수 있는 값이다.

 

a1 < a2 < ... < an 이고 ai < x <= ai+1 이라고 할 때

 

|x - a1| + ... + |x- an| = Sn - 2(a1+a2+...+ai) -(n - 2i)x

 

이기 때문에 변곡점은 n - 2i > 0 에서 n - 2i <= 0 으로 바뀌는 i 이고 

 

x = a_i/2 , y = b_i/2 

일 때 최소 거리 합을 얻을 수 있다.

 

 

풀이코드

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

        int n = Integer.parseInt(br.readLine().split(" ")[0]);
        int[] x = new int[n];
        int[] y = new int[n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int xi = Integer.parseInt(st.nextToken());
            int yi  = Integer.parseInt(st.nextToken());

            x[i] = xi;
            y[i] = yi;
        }

        Arrays.sort(x);
        Arrays.sort(y);

        int mid = n / 2;
        long result = 0;
        for (int i = 0; i < n; i++) {
            result += Math.abs(x[i] - x[mid]) + Math.abs(y[i] - y[mid]);
        }

        System.out.println(result);
    }
}