BOJ 2285 : 우체국

• 문제 링크 : boj.kr/2285
• 난이도 : G4
• 태그 : 그리디, 정렬

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 987654321
#define int long long

using namespace std;

using ld = long double;
using pii = pair<int,int>;

template <typename T1, typename T2>
istream& operator>>(istream & ist, pair<T1,T2> &p) {
    ist >> p.first >> p.second;
    return ist;
}
template <typename T>
istream& operator>>(istream & ist, vector<T> &arr) {
    for(auto &u : arr) ist >> u;
    return ist;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<pii> arr(n);
    cin >> arr;

    sort(all(arr));

    int total = 0;  
    for(auto u : arr) total += u.second;
    int sum = 0;
    for(auto u : arr) {
        sum += u.second;
        if(sum * 2 >= total) {
            cout << u.first;
            return 0;
        }
    }

    return 0;
}

---

풀이

우체국이 어떤 위치에서 오른쪽으로 이동한다면, 그 위치와 왼쪽에 있는 사람의 수만큼 거리의 합은 늘어나고, 오른쪽에 있는 사람의 수만큼 거리의 합은 줄어든다. 이 증감량이 바뀌는 지점은 마을의 위치와 같다. 따라서 각 마을의 위치만 확인해보고, 지나친 마을의 사람 수의 합이 전체 사람 수의 합의 과반수가 되었다면 종료하면 된다.