[백준] 2141 - 우체국

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

2141번: 우체국

처음에 고민을 많이 하다 수학으로 풀었었습니다. 우체국의 위치를 x 로 잡고 각 마을과의 거리와 인구를 곱하면 여러 절댓값으로 이루어진 그래프가 그려지고 그 그래프의 극소점이 답이 되었습니다. 하지만 알고리즘 분류에 그리디가 있는 것을 보고 다른 풀이를 참고하다 더 간단한 방법이 있다는 것을 알게 되었습니다.

 

아래 그림과 같이 어느 위치의 왼쪽의 인구합을 l, 오른쪽을 r로 정의하면 l > r 일때는 왼쪽으로 가면 거리합이 줄고 l < r 일때는 오른쪽으로, l = r 일때는 어느쪽으로 가나 같게 됩니다. 그러면 l = r 인 상황은 인접한 두 마을 중 왼쪽이 답이 되고 l > r or l < r 인 상황은 그 사이에 있는 마을에 우체국이 있어야 최소합이 됩니다. 그렇기에 이 문제는 인구 총합을 구한 후 왼쪽에서부터 더해가면서 그 절반을 넘는 마을이 정답이 됩니다. 그리고 총합이 홀수인 상황도 생각해 (r + 1) / 2 를 비교해줍니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

vector<pair<ll, ll>> v;
ll n, a, b, l, r;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        v.emplace_back(a, b);
        r += b;
    }
    sort(v.begin(), v.end());

    for (int i = 0; i < n; i++) {
        l += v[i].second;
        if (l >= (r + 1) / 2) {
            cout << v[i].first << "\n";
            break;
        }
    }

    return 0;
}