[백준,c++] 2141번 - 우체국

문제

2141번: 우체국

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long int

using namespace std;

ll sum[100001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    ll N; cin>>N;
    vector<pair<ll, ll>> v;
    for(int i=0; i<N; i++){
        ll a, b; cin>>a>>b;
        v.push_back({a, b});
    }
    sort(v.begin(), v.end());
    sum[0] = v[0].second;
    for(int i=1; i<N; i++) sum[i] = sum[i-1] + v[i].second; // 사람 수 누적 합
    
    ll start = 0, end = N-1;
    ll idx = 1e9;
    while(start <= end){
        ll mid = (start + end) / 2;
        if(sum[mid] >= sum[N-1] - sum[mid]){
            end = mid - 1;
            idx = min(idx, v[mid].first);
        }
        else start = mid + 1;
    }
    cout<<idx;
}

 

풀이

문제 분류는 그리디로 되어있는데 저는 누적합과 이분 탐색을 이용하여 풀었습니다.

1. 각 위치까지의 사람 수를 누적합을 통해 갱신합니다.
2. 이분탐색을 통해 우체국을 세울 위치를 정합니다.
3. 현재 위치 까지 더한 사람 수가 우측의 사람들 수 보다 크다면 한 칸 더 좌측으로 가는 것이 유리합니다. 
4. 현재 위치까지 더한 사람 수보다 우측의 사람들 수가 더 크다면 우측으로 한 칸 더 가는 것이 유리합니다.
5. 이를 통해 최적의 위치를 찾습니다.