# 2141. 우체국

관련 알고리즘 : 누적합, 이분탐색

 

문제 링크 : https://www.acmicpc.net/problem/2141

2141번: 우체국

---

문제 풀이

문제 조건을 살펴보면,

• 수직선상 N개 마을
• i번째 마을 위치 : X[i]
• i번째 마을 사람 수 : A[i]
• |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000
• 가능한 경우가 여러 가지 => 더 작은 위치 출력

▶ 우체국 위치 : "각 사람들까지의 거리의 합" 이 최소가 되는 곳

 

제일 왼쪽 마을부터 누적으로 사람 수가 중간지점이 되는 마을에 우체국을 설치해야 한다는 감은 왔는데,

거리를 따지지 않고 사람 수만 따지는 것이 맞는 풀이인지 확신이 들지 않았다.

백준 질문게시판에서 해당 의문에 대한 답을 찾을 수 있었다.

 

우체국과 마을의 거리가 1씩 멀어질 때마다 마을 사람 수의 배만큼 영향을 주기 때문에, 

우체국을 기준으로 양쪽 사람 수가 균형이 맞아야 한다.

또한, 우체국은 마을이 위치한 곳에 위치해야 한다. 마을이 없는 위치에 생긴다면 거리 낭비만 발생한다.

 

따라서, 누적합과 이분탐색을 이용하여 문제를 해결할 수 있었다.

---

C++ 코드

#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);
    cout.tie(0);

    ll n;
    cin >> n;
    vector<pair<ll, ll>> v;

    for(int i=0; i<n; i++){
        ll x;
        ll a;
        cin >> x >> a;
        v.push_back({x, a}); // 우체국 위치와 인구 수 묶기
    }

    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;
    ll end = n-1;
    ll index = 1e9; // 최대범위 1,000,000,000

    // 이분탐색
    while(start < end){
        ll mid = (start + end) / 2;

        if(sum[mid] >= sum[n-1] - sum[mid]){
            end = mid -1;
            index = min(index, v[mid].first); // 더 작은 위치 출력
        }
        else start = mid + 1;
    }
    cout << index;
}