[BOJ/백준][Gold4] 2141 : 우체국 (C++)

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

2141번: 우체국

 

 

[난이도] Gold4
[유형] Greedy

[풀이]
거리의 합이 최소가 될때 유리하게 만들기 위해서는

우체국의 위치를 x라고 했을 때, x에 마을이 많을수록,
x를 기준으로 좌우에 퍼져있는 우체국의 수가 비슷할수록 유리합니다.

결국 마을위 위치를 기준으로 정렬한 뒤,
1~N 마을을 순회하면서 사람 수를 cur에 더해나갑니다.
그러다 cur>=(sum(전체 사람 수)+1)/2 를 만족하는 순간의 i가 우체국이 설치되었을 때
가장 유리한 마을의 index입니다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
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;
        }
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2141.cpp