[BOJ / C++] 2141번 : 우체국

문제

수직선과 같은 일직선상에 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 이며 모든 입력은 정수이다.

출력

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

Solved.ac 레벨

골드 IV

풀이

계속 런타임 에러 (Out of bounds) 때문에 고생했던 문제. 마을 간의 거리가 아니라 사람 간의 거리라 마을 간의 거리를 고려할 필요가 없다는 것도 알고, 마을 순으로 정렬하여 사람 간의 거리를 이분 탐색했을 때 최소가 되는 지점에 우체국을 세워야 한다는 것 까지도 캐치를 했는데 x[i]와 a[i]의 범위 때문에 합이 int 범위를 넘어설 수 있다는 점을 간과했다.

 

마을의 좌표와 마을 당 인구 수를 입력받아 마을의 좌표 순으로 정렬 후 가운데 좌표를 찾아 이분탐색을 진행하여 가운데 좌표 기준으로 왼쪽 좌표의 누적합과 오른쪽 좌표의 누적합의 차이가 최소가 되는 지점을 출력했다.

 

런타임 에러 때문에 다른 분들의 풀이를 참고하고 나서야 int 범위를 벗어난걸 눈치 챈 나는....

Code

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    long long ans = 9876543210;
    vector<pair<long long, long long>> v;
    vector<long long> sum;

    cin >> n;

    for(int i = 0; i < n; i++) {
        long long x, a;
        cin >> x >> a;
        v.push_back({x, a});
    }

    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);
    }

    long long s = 0, e = n - 1;

    while(s <= e) {
        long long mid = (s + e) / 2;
        long long lSum = sum[mid];
        long long rSum = sum[n - 1] - sum[mid];

        if(lSum >= rSum) {
            e = mid - 1;
            ans = min(ans, v[mid].first);
        } else{
            s = mid + 1;
        };
    }

    cout << ans << "\n";


    return 0;
}

2141번: 우체국