(C++) - 백준(BOJ) 2141번 : 우체국 답

www.acmicpc.net/problem/2141

2141번: 우체국

 이분탐색 문제였습니다. 지문이 헷갈렸는데 먼저 우체국은 무조건 마을이 있는 위치에 세워야 합니다. 1.5 위치같은 소수점 위치에 세우거나 마을이 존재하지 않는 위치에 우체국을 만드는 경우는 없습니다. 또한 우체국을 세운 위치로부터 왼쪽 끝 마을에 위치한 사람들까지의 합, 우체국을 세운 위치 바로 다음 마을부터 오른쪽 끝 마을에 위치한 사람들까지의 합이 서로 균형(최대한 같아지는)을 이루도록 이분탐색을 시행해야 합니다.

 

풀이방법

 1. 마을의 위치가 순서대로 들어오지 않을 경우를 대비해 마을 위치를 오름차순으로 sort해줍니다.

 2. 가장 왼쪽에 위치한 마을부터 현재위치의 마을까지의 누적합을 저장해줍니다.

 3. 이분탐색 시행

   3-1. mid번에 저장된 위치에 우체국을 만들었다고 가정했을 때 0번째 마을부터 mid번째 마을까지의 사람들 합은 sum[mid]입니다. 그리고 mid+1번째 마을부터 n-1번째 마을까지 사람들의 합은 sum[n-1] - sum[mid]가 됩니다.

   3-2. 만약 우체국을 기점으로 왼쪽편 사람들의 합이 오른편 사람들의 합 이상이라면 우체국의 위치는 왼편이 유리하므로 r = mid-1입니다. 그 후 mid위치와 구하려는 위치 중 최소값을 비교 후 갱신해줍니다. 반대의 경우는 오른편에 우체국을 건설하는 것이 유리하기 때문에 l = mid+1입니다.

  

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
vector <pair<int,int>>x;
vector<ll> sum;

int binarySearch(){
    int l = 0;
    int r = n - 1;
    int pos = 0x7f7f7f7f;
    while(l<=r){
        int mid = (l+r)/2;
        ll leftSum = sum[mid];
        ll rightSum = sum[n - 1] - sum[mid];
        if(leftSum >= rightSum){
            r = mid - 1;
            pos = min(pos, x[mid].first);
        }else{
            l = mid + 1;
        }
    }
    return pos;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) {
        int pos, peopleNum;
        cin >> pos >> peopleNum;
        x.push_back({pos,peopleNum});
    }
    sort(x.begin(),x.end());

    sum.push_back( x[0].second);
    for(ll i = 1; i < n; i++)
        sum.push_back(sum[i-1] + x[i].second);
    cout << binarySearch();
}

 

Test Case

백준 질문게시판에 있던 반례들을 추가해보았습니다.

 

input

2
1 3
2 3

답 : 1

 

input

2
1 1
2 2

답 : 2