[BOJ] 우체국 2141번 C++

 

문제

수직선과 같은 일직선상에 N개의 마을이 위치해 있다. i번째 마을은 X[i]에 위치해 있으며, A[i]명의 사람이 살고 있다.

이 마을들을 위해서 우체국을 하나 세우려고 하는데, 그 위치를 어느 곳으로 할지를 현재 고민 중이다. 고민 끝에 나라에서는 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우기로 결정하였다. 우체국을 세울 위치를 구하는 프로그램을 작성하시오.

각 마을까지의 거리의 합이 아니라, 각 사람까지의 거리의 합임에 유의한다

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.

출력

 

첫째 줄에 우체국의 위치를 출력한다. 가능한 경우가 여러 가지인 경우에는 더 작은 위치를 출력하도록 한다.

 

접근 방식

 

문제에서 각 사람까지의 거리의 합이 최소가 되는 위치를 구해야 함을 주의해야 한다

따라서 누적합을 이용해 최소가 되는 위치를 구할 수 있다

 

최소가 되는 우체국의 위치는 인구수가 우체국을 기준으로 절반씩 나눠지는 위치다

따라서 총 인구수를 구한다음, 누적 인구수를 구하면서 절반으로 나눠지는 위치에 우체국을 설치하면 된다!

 

 

코드

 

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

typedef long long ll;

int main() {
    int N; cin>>N;
    vector<pair<int,int>> v(N+1);
    ll total = 0;
    for(int i=1; i<=N; i++) {
        int x,a; cin>>x>>a;
        v[i] = {x,a};
        total += a;
    }
    sort(v.begin()+1, v.end());

    ll population = 0;

    for(int i=1; i<=N; i++) {
        population += v[i].second;
        if(population >= (total + 1) / 2) {
            cout<<v[i].first;
            break;

        }
    }
    


}

 

주의할 점은 인덱스가 1부터 시작하는데

sort 메서드를 v.begin()이 아닌 v.begin() + 1로 잡아주어야 한다는 점이다!!!