백준 7571 점모으기

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

7571번: 점 모으기

 

 

위와 같이 위치된 점들을 하나의 점으로 모았을때 최소거리를 구하는 문제다.

점들의 x좌표, y좌표를 각각 xx , yy라는 배열에 저장하고 이점들을 모두

(p,q) 라는 점에 모았을때 거리 D(p,q)를 계산한다고 생각해보면

 

D(p,q) = |xx[0] - p| +  |xx[1] -p| + .... |xx[n-1] -p| + |yy[0] -q| + |yy[1] -q| + |yy[2]-q| + .... |yy[n-1]-q| 라는 것을 구할수 있다. (단, |A|는 A의 절대값)

 

D(p,q)가 최소가 되기 위해서는 p ,q 는 x[0]~ x[n-1] y[0]~ y[n-1]의 중앙값 이여야한다.(평균이 아니라 중앙값)

보통 x좌표, y좌표의 평균을 구해야된다고 생각하는 경우가 많지만 다음과같은 경우를 생각해보자

 

100 3

1 1

1 3

1 100

x좌표가 모두 같으므로 당연히 p=1이고 q를 평균으로 구한다고 생각하면

 

q=(1+3+100)/3 = 34이다.

D(1,34)= 0+0+0 + |1-34| + |3-34|+ |100-34| = 33+ 31+ 66 = 120이다.

하지만 q를 중앙값으로 구한다고 생각하면 중앙값은 3이므로

D(1,3) = 0+0+0 + |1-3| + |3-3| + |100-3| = 2+0+97 =99로 더 작은 것을 알수 있다.

 

사실 당연한것이다. 

우리는 중학교때 |1-x| + |x-2| + |10-x|와 같은 절대값이 포함된 방정식을 풀어봤을 것이다.

이 방정식은 x<1일때는 1-x + 2-x + 10-x = 13 -3x

1<=x<2일때는 x-1+ 2-x + 10-x = 11-x

2<=x<10일때는 x-1+x-2+10-x = x+7

x>=10일때는 1-x + x-2 + x- 10 = x -11이므로

 

와 같은 그래프를 나타낸다.

그러므로 이 그래프의 최소값은 중앙값인 x= 2에서 최소값이다.

 

따라서 x,y의 중앙값을 구해준다음 거리를 각각 더해주면 답이다 ~

package 백준;

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

public class 점모으기 {
	public static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner();
		int N = sc.nextInt();
		int M= sc.nextInt();
		
		ArrayList <Integer> xx = new ArrayList <Integer>();
		ArrayList <Integer> yy = new ArrayList <Integer>();
		
		for(int i =0 ;i <M;i++) {
			xx.add(sc.nextInt());
			yy.add(sc.nextInt());
		}
		
		Collections.sort(xx);
		Collections.sort(yy);
		int p=1,q=1;
		if(M%2==1) {
			p = xx.get(M/2);
			q = yy.get(M/2);
		}else {
			p = (xx.get(M/2)+xx.get(M/2-1))/2;
			q= (yy.get(M/2)+yy.get(M/2-1))/2;
		}
		
		int answer= 0;
		
		for(int i =0 ;i<M;i++) {
			answer+= Math.abs(p-xx.get(i));
			answer+= Math.abs(q-yy.get(i));

		}
		System.out.println(answer);
	}

}