[백준 2141번] 우체국 (C++)

문제링크 : https://www.acmicpc.net/problem/2141

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N;
ll sum = 0;
vector<pii>v;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<N; i++)
    {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
        sum+=b;
    }

    sort(v.begin(), v.end());
    ll tmp = 0;
    for(int i=0; i<v.size(); i++)
    {
        tmp += v[i].second;
        if(tmp >= (sum+1)/2) //정렬된 상태의 중앙값 출력
        {
            cout << v[i].first;
            break;
        }
    }
    
    return 0;
}

 

지문이 제대로 이해되지 않았던 문제이다.

우체국 위치를 기준으로 왼쪽 사람수와 오른쪽 사람수를 최소로 맞춰주어야 한다.

이를 위해 입력받은 값을 정렬해주고, 정렬된 값의 중앙 값을 체크해주면 된다.

 

사람 수를 입력받으며 미리 누적합을 구해놓고 (범위로 인해 long long 사용) 해당 누적합을 기준으로 정렬된 첫 번째부터 합을 새롭게 구하면서 해당 합 절반이 넘어가는 위치를 출력해주면 된다.