백준 14400 - 편의점 2

www.acmicpc.net/problem/14400

 

새로 세우려는 편의점과 모든 주요 고객들의 맨하탄 거리가 최소가 되는 값을 찾아야 한다.

 

일직선 그래프의 경우에 대해 먼저 생각해보자.

 

일직선 그래프에서 모든 정점들과의 거리가 최소가 되는 좌표는 가운데에 위치한 점, 좌표들의 중앙값일 것이다.

 

이를 평면 그래프로 확장하면 X축에서 x좌표의 중앙값과 Y축에서 y좌표의 중앙값이 맨하탄 거리의 합을 최소로 하는 좌표가 된다.

 

정렬을 통해 각 축의 중앙값을 찾아 좌표를 만들고 해당 좌표와 고객들 사이 맨하탄 거리를 더해주면 답이 나온다.

 

전체코드 - 값이 int 범위를 넘어섬에 유의하자.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

bool cmp(pair<int, int> &l, pair<int, int> &r) { return l.second < r.second; }

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<pair<int, int>> convi(n);
    
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        convi[i] = {a, b};
    }
    
    sort(convi.begin(), convi.end());
    int l = convi[(n - 1) / 2].first;
    sort(convi.begin(), convi.end(), cmp);
    int r = convi[(n - 1) / 2].second;
    
    ll ans = 0;
    for (int j = 0; j < n; ++j)
        ans += abs(l - convi[j].first) + abs(r - convi[j].second);
    
    cout << ans;
}