백준 7571번: 점 모으기

문제 설명

• https://www.acmicpc.net/problem/7571
• 모든 점들을 하나의 위치로 모을 때 드는 이동거리의 합의 최소값을 구하는 문제입니다.

접근법

• 혼자서는 이 문제를 못풀었다. 평균값을 구하는 방법으로 풀었는데 틀렸고, 이후 방법을 생각했는데 도무지 모르겠어서 다른 풀이를 찾아봤다. 풀이를 봤지만 명확하게 이해는 되지 않았다.

• 점의 좌표가 (a1,b1),(a2,b2),...일 때 어떤 칸(x,y)까지 모든 점이 이동하는 데 걸리는 이동거리는 |x-a1|+|x-a2|+...+|y-b1|+|y-b2|+...다.

  • 즉 |x-a1|+|x-a2|+...+|y-b1|+|y-b2|+...의 최솟값을 구해야 한다.
  • 여기서 x는 y의 값에 관계없이 아무 값이나 고를 수 있고 y역시 마찬가지다. 즉 x와y는 아무런 영향을 받기 때문에 |x-a1|+|x-a2|+...의 최솟값과 |y-b1|+|y-b2|+...의 최솟값을 구한 뒤 더하면 전체 최솟값이 된다.
  • 그리고 이 절대값의 덧셈에서 최소를 구하는 방법은 x의 값이 a1,a2...,an의 중앙값일 때 최소값이 된다고 한다.(그래프를 그려보면 알 수 있음)
    • 참고 사이트: https://wjdtn7823.tistory.com/22

정답

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

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());
		int M = Integer.parseInt(st.nextToken());
		List<Integer> xList = new ArrayList<Integer>();
		List<Integer> yList = new ArrayList<Integer>();
		
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			xList.add(x);
			yList.add(y);
		}
		Collections.sort(xList);
		Collections.sort(yList);
		int midIdx = (M/2);
		int midX = xList.get(midIdx);
		int midY = yList.get(midIdx);
		int Score = 0;
		for (int i = 0; i < M; i++) {
			Score += Math.abs(midX-xList.get(i));
			Score += Math.abs(midY-yList.get(i));
		}
		System.out.println(Score);
		
	}
	
	
}