[BOJ 7571 // C++] 점 모으기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 7571번 문제인 점 모으기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/7571

7571번: 점 모으기

이 문제는 다음 두가지 생각을 하면 간단히 풀 수 있다.

(1) 점을 특정 좌표로 모으기 위해 필요한 좌우방향 움직임 횟수와 상하방향 움직임 횟수는 서로 영향을 주지 않는다.

(2) 모으려는 점의 x(또는 y)좌표를 기준으로 좌우(또는 상하)에 있는 점의 개수의 차이가 최소여야한다. 이 성질을 가지고 있는 x(또는 y)좌표를 구하는 방법은 정렬을 이용하는 것이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;

int x[100001];
int y[100001];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    int tempx, tempy;
    for (int i = 1;i <= M;i++) {
        cin >> tempx >> tempy;
        x[i] = tempx;
        y[i] = tempy;
    }

    sort(x + 1, x + M+1); // 정렬
    sort(y + 1, y + M+1);
    int xmid = x[(M + 1) / 2]; // 원하는 성질을 가진 x좌표와 y좌표
    int ymid = y[(M + 1) / 2];
    int ans = 0;
    for (int i = 1;i <= M;i++) { // 구한 좌표로 답 구하기
        ans += abs(x[i] - xmid) + abs(y[i] - ymid);
    }

    cout << ans;

    return 0;
}