[BOJ] 편의점 2 14400번 C++

 

 

문제

영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고객들이 어느 위치에 존재하는지 파악을 하였고, 모든 고객들의 거리의 합을 최소로 하려한다. 두 위치 (x1, y1), (x2, y2)의 거리는 |x1 - x2| + |y1 - y2|로 정의한다.

n명의 주요 고객들의 위치 (xi, yi)이 주어질 때, 모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 세울 때, 그 최소 거리 합을 출력하시오.

입력

첫째 줄에는 주요 고객들의 수 n이 주어진다.

다음 n줄에는 i번 고객의 위치 xi, yi가 주어진다.

출력

모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 세울 때, 그 최소 거리 합을 출력하시오.

 

접근 방식

 

생각보다 간단하게 풀이할 수 있다.

모든 좌표의 x,y를 분리해 정렬한 다음

가운데 좌표를 이용하면 최소 거리의 합을 구할 수 있다.

이때, 주의할 점은 최소 거리의 합이 int 형의 범위를 넘을 수 있다는 것이다.

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n; 
    cin >> n;
    vector<pair<int, int>> v(n);
    vector<int> x(n), y(n);

    for(int i = 0; i < n; i++) {
        cin >> v[i].first >> v[i].second;
        x[i] = v[i].first;
        y[i] = v[i].second;
    } 

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    int mid_x = x[n / 2];
    int mid_y = y[n / 2];

    long long ans = 0;

    for(auto& c : v) {
        ans += abs(c.first - mid_x) + abs(c.second - mid_y);
    }

    cout << ans;
}