[BOJ]2141-우체국

2141

결과코드

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

using namespace std;

int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    int N;
    vector <pair<long long, long long>> vil;
    vector<long long>sum;

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int tmp1, tmp2;
        cin >> tmp1 >> tmp2;
        vil.push_back(make_pair(tmp1, tmp2));
    }

    sort(vil.begin(), vil.end());

    sum.push_back(vil[0].second); 
    for (int i = 1; i < N; i++)
    {
        long long tmp = vil[i].second;
        sum.push_back(sum[i-1] + tmp);
    }

    int start = 0;
    int end = N-1;
    int mid;
    int res = vil[N-1].first;
    while (start <= end)
    {
        mid = (start + end) / 2;

        if (sum[mid] >= sum[N - 1] - sum[mid])
        {
            end = mid - 1;
            if (res > vil[mid].first)
            {
                res = vil[mid].first;
            }
        }
        else
        {
            start = mid + 1;
        }
        
    }

    cout << res;

}

풀이를 보고 말았어요.

누적합과 이분 탐색으로 푸는 방법이 있어서 참고했다.

이 문제의 핵심은 우체국 좌우의 사람이 균등하게 있어야 최적해를 낸다는 것.

그리디로 푸는 방법은 사람 수의 중간값을 구해 첫 마을부터 사람의 수를 더해가 처음으로 중간값과 같아지거나 커지는 마을의 위치를 도출한다.

참고자료

2141 이분탐색 풀이
2141 그리디 중간값 풀이