[BOJ] 2141번 : 우체국

문제 링크 : 백준 2141번

[문제 접근]

그리디 알고리즘을 이용해야 할 것 같은데 방법이 도저히 생각이 안나서 다른 풀이를 참고했다.
각 사람들까지 거리의 합이 최소가 되려면 우체국을 설치하는 위치 기준으로 양쪽에 있는 인구가 비슷해야한다.

1. 위치 순으로 정렬 후 1번째 마을부터 탐색하면서 인구수를 더해준다.
2. 탐색 중에 더해진 인구수가 전체 인구수의 반절을 넘어갈 때가 양쪽에 있는 인구수가 가장 비슷하게 된다.

⭐️ 이분 탐색으로도 풀 수 있는 것 같다.

[소스 코드]

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

using namespace std;
int n;
vector<pair<long long, long long> > arr;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    long long total=0;
    for(int i=0 ; i<n ; i++) {
        long long x,a;
        cin >> x >> a;
        arr.push_back(make_pair(x, a));
        total += a;
    }
    sort(arr.begin(), arr.end());
    long long temp=0;
    for(int i=0 ; i<n ; i++) {
        temp += arr[i].second;
        if(temp>=(total+1)/2) { // 인구 밀집도의 중간 => 각 사람들까지 거리의 합이 최소가 되는 위치
            cout << arr[i].first << "\n";
            break;
        }
    }
    
    return 0;
}