백준 7571번 [점 모으기](C++) -yes6686- 티스토리

백준 문제 풀이: 7571 (점 모으기)

---

문제 링크: https://www.acmicpc.net/problem/7571

문제 설명:

2차원 격자 평면 위에 m개의 점이 주어질 때, 이 점들을 한 위치로 옮기는 데 필요한 최소 이동 거리의 합을 구하는 문제입니다. 각 점은 상하좌우 방향으로만 움직일 수 있으며, 한 점을 다른 점의 위치로 옮길 수 있습니다.

최소 이동 거리의 합을 구하기 위해서는 모든 점을 특정 위치로 이동시킬 때 거리 합이 최소가 되는 좌표를 찾아야 합니다. 이 좌표는 각각 x좌표와 y좌표의 **중앙값(median)**을 기준으로 결정됩니다.

---

문제 해결 코드

// 7571번: 점 모으기
// 모든 점을 median 좌표로 이동시키는 것이 최적해

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int arrx[100001];
int arry[100001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    // 각 점의 좌표 입력
    for (int i = 0; i < m; i++) {
        cin >> arrx[i] >> arry[i];
    }

    // x좌표, y좌표 정렬하여 중앙값 구하기
    sort(arrx, arrx + m);
    sort(arry, arry + m);

    int mx = arrx[m / 2];
    int my = arry[m / 2];

    // 모든 점을 (mx, my)로 이동할 때의 총 거리 계산
    int ans = 0;
    for (int i = 0; i < m; i++) {
        ans += abs(arrx[i] - mx) + abs(arry[i] - my);
    }

    cout << ans << '\n';
}

---

코드 설명

• 핵심 알고리즘: 중앙값(Median)을 이용한 최소 거리 전략
• 이유: 1차원에서 여러 점을 한 점으로 이동할 때, 거리 합이 최소가 되는 위치는 중앙값입니다. 2차원 격자에서도 x축, y축 각각 독립적으로 적용할 수 있습니다.
• 구현 세부사항:
  • sort(arrx, arrx + m): x좌표 오름차순 정렬
  • arrx[m / 2]: x좌표의 중앙값
  • abs(arrx[i] - mx): 각 점의 x축 거리
• 시간 복잡도 분석:O(m log m) — 정렬 2번 + 선형 거리 계산

---

결과

m개의 점을 한 지점으로 옮기는 데 필요한 최소 이동 거리의 합을 출력합니다.

예시 입력:
5 3
1 2
2 4
5 1

예시 출력:
7

설명: 중앙값 좌표 (2, 2) → 이동 거리 합: |1-2|+|2-2| + |2-2|+|4-2| + |5-2|+|1-2| = 1 + 0 + 0 + 2 + 3 + 1 = 7

다른 접근 방식이나 궁금한 점이 있다면 댓글로 자유롭게 남겨주세요!