BOJ 백준온라인져지 7571 점 모으기 풀이

1. 처음에는 평균을 구해서 한다고 생각했다.

2. 근데 만약 평균값을 구하는건데 10000, 10000 이 10000개 1, 1이 1개면

3. 평균값만큼 이동을 해야된다.

4. 그래서 중앙값을 찾아서 거기로 모이는걸 생각했다.

5. x, y 를 각각 따로보면 각각 정렬해서 구하고 중간값만큼 이동

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/problem/7571
	* BOJ 백준온라인져지 7571 점 모으기 풀이
	*/
	public class Main {
	public static void main (String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String str1[] = br.readLine().split(" ");
	int N = Integer.parseInt(str1[0]);
	int M = Integer.parseInt(str1[1]);
	int dotX[] = new int[M];
	int dotY[] = new int[M];
	for (int i = 0; i < M; i++) {
	String str2[] = br.readLine().split(" ");
	int x = Integer.parseInt(str2[0]);
	int y = Integer.parseInt(str2[1]);
	dotX[i] = x;
	dotY[i] = y;
	}
	Arrays.sort(dotX);
	Arrays.sort(dotY);
	int result = 0;
	int x = dotX[M / 2];
	int y = dotY[M / 2];
	for (int i = 0; i < M; i++) {
	result += Math.abs(dotX[i] - x);
	result += Math.abs(dotY[i] - y);
	}
	bw.write(String.valueOf(result));
	bw.flush();
	}
	}

view raw Main.java hosted with ❤ by GitHub

문제

행의 크기와 열의 크기가 각각 N인 격자공간에 M개의 점이 있다. N = 4이고 M = 4인 경우의 예가 아래에 있다. 격자공간 왼쪽의 숫자는 행 번호이며, 위의 숫자는 열 번호를 나타낸다. 그리고 격자공간내의 각 사각형의 위치는 (행 번호, 열 번호)로 표시한다

이제 격자공간에 있는 모든 점들을 하나의 사각형 안으로 모으려고 한다. 어떤 점을 움직일 때는 그 점이 들어있는 사각형에서 상하좌우로 인접한 사각형으로만 움직일 수 있다.

여기에서는 격자공간내의 한 사각형으로 모든 점들을 모을 때 각 점이 움직인 거리의 합을 고려한다. 예를 들어, 위의 점들을 (3,2)에 있는 사각형으로 모을 때 최단거리로 점들을 이동시킨다면 (1,2)에 있는 점의 이동거리는 2이고, (3,1)과 (4,2)에 있는 점의 이동거리는 각각 1이며, (1,4) 에 있는 점의 이동거리는 4이므로 점들이 움직인 거리의 합은 8이다. 또, 위의 모든 점들을 (1,2)의 위치로 모을 때도 점들이 이동한 거리의 합이 8 임을 알 수 있다. 위의 예에서는 점들을 어떤 하나의 사각형으로 모을 때 이동거리의 합이 8보다 작게 되는 사각형은 없다.

이 문제는 주어진 격자공간에 있는 모든 점들을 하나의 사각형으로 모을 때 드는 이동거리의 합의 최솟값을 구하는 것이다. 주어진 격자공간에서는 하나의 사각형에 여러 개의 점들이 들어 있을 수도 있고, 점들을 모을 때는 어떤 점이 들어 있는 사각형으로도 모을 수 있다고 가정한다.

입력

첫 줄에는 격자공간의 크기와 점들의 개수를 나타내는 두 정수 N과 M이 하나의 공백을 사이에 두고 주어진다. 다음의 M줄에는 각 줄마다 격자공간내의 점의 위치를 나타내는 두 개의 정수가 하나의 공백을 사이에 두고 주어진다. 단, N의 크기는 1이상 10,000이하이고, M의 크기는 1이상 100,000이하이다.

출력

여러분은 모든 점들을 하나의 사각형으로 모을 때 드는 이동거리의 합의 최솟값을 출력해야 한다.