백준 14400 편의점 2

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

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

vector<int> X;
vector<int> Y;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; 
    long long ans = 0;
    cin >> n;

    X.resize(n);
    Y.resize(n);


    for (int i = 0; i < n; i++) {
        cin >> X[i] >> Y[i];
    }

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());

    int ansX = X[(n - 1) / 2];
    int ansY = Y[(n - 1) / 2];

    for (int i = 0; i < n; i++) {
        ans += abs(ansX - X[i]) + abs(ansY - Y[i]);
    }

    cout << ans;

    return 0;
}

1. 문제

n개의 집의 2차원 상의 좌표가 주어지고, 여기 편의점을 세우려 한다. 편의점과의 거리는 맨허튼 거리로 정의하고, 모든 집과 편의점 사이의 거리가 최소가 되는 곳에 편의점을 세우려 할 때, 그 거리를 구하라.

2. 풀이

    long long ans = 0;

x, y가 -100만부터 100만까지, n이 10만까지이므로 int 범위를 초과할 수 있다. long long으로 선언해주자.

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());

    int ansX = X[(n - 1) / 2];
    int ansY = Y[(n - 1) / 2];

X좌표와 Y좌표를 각각 정렬하고, 각 좌표의 중간값으로 편의점을 설정한다.

    for (int i = 0; i < n; i++) {
        ans += abs(ansX - X[i]) + abs(ansY - Y[i]);
    }

그 후 해당 편의점의 좌표와 각 집에 대하여 맨허튼 거리를 계산하고 더하여 이를 출력하면 정답을 구할 수 있다.