[백준/C++] 2141번 우체국

https://www.acmicpc.net/problem/2141

2141번: 우체국

가장 공평한 곳에 우체국을 설치한다..! 라고 문제를 이해한다면 풀이법에 접근하기 훨씬 간단해진다.

보통 친구들과 약속 장소를 정할 때, 중간 지점일 수록 그리고 친구의 수가 많은 곳일 수록! 위 2가지로 정할 것이다.

우리는 이러한 룰을 문제에 적용시켜볼 것이다.

​

먼저 마을 번호를 기준으로 오름차순 정렬한다. 그리고 마을에 사는 사람의 수를 기준으로 우체국을 세우기 위해 누적합을 계산한다.

(사실 O(n^2)의 시간복잡도를 이용해 완전탐색할 수도 있지만 입력의 크기가 10만이므로 그건 불가능..!)

​

누적합을 이용하여 이분탐색을 실시한다.

- 만약 왼쪽 마을 사람들의 수가 더 많다면 왼쪽에 우체국을 세우는 것이 이득이므로, right를 mid-1로 조정해준다.

그리고 기왕이면 가능한 경우가 여러가지이면 더 작은 위치가 출력되라고 하였으므로 이 때 답을 갱신해준다.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

vector<pair<int,int>> v;
vector<ll> sum;
int n;

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

    cin >> n;

    for(int i=0;i<n;i++){
        int pos,people;
        cin >> pos >> people;
        v.push_back({pos, people});
    }
    // 마을 위치 오름차순 정렬
    sort(v.begin(),v.end());

    // 첫번째 마을부터 현재 마을까지의 사람 누적합 저장
    sum.push_back(v[0].second);
    for(int i=1; i<n;i++){
        sum.push_back(sum[i-1] + v[i].second);
    }

    int left = 0;
    int right = n-1;
    int ans = 0x7f7f7f7f;
    while(left<=right){
        int mid = (left+right)/2;
        ll lsum = sum[mid];
        ll rsum = sum[n-1] - sum[mid];

        if(lsum >=rsum){
            right = mid-1;
            ans = min(ans,v[mid].first);
        }
        else{
            left = mid+1;
        }
    }
    cout << ans;
    return 0;
}

아래처럼 풀수도 있다. 결국 마을 위치를 기준으로 정렬한 뒤, 1~N 마을을 순회하면서 사람 수를 cur에 더해 나간다.

그러다 cur>=(sum(전체 사람 수)+1)/2 를 만족하는 순간의 i가 우체국이 설치되었을 때가 (= 현재 사람 수가 전체 사람 수의 절반보다 크거나 같아질 때) 가장 유리한 마을의 index이다.

using ll = long long;
int N;
pair<ll,ll> xa[100001];
 
int main(){
    scanf("%d",&N);
    ll sum=0;
    for(int i=1;i<=N;i++) {
        scanf("%lld%lld",&xa[i].first,&xa[i].second);
        sum+=xa[i].second;
    }
    sort(xa+1,xa+N+1);
 
    ll cur=0;
    for(int i=1;i<=N;i++){
        cur+=xa[i].second;
        if(cur>=(sum+1)/2) {
            printf("%d",xa[i].first);
            break;
        }
    }
}