백준 2141 : 우체국

각 사람까지의 거리의 합이 최소가 되는 우체국의 위치를 구해야 하는 문제이다.

---

오늘 재체점에 갑자기 틀렸습니다. 가 떠서 급히 다시 푼 문제이다.

 

이런;;

우체국이 설치될 위치는 전체 인구의 중앙이 되는 지점입니다. 이는 총 인구의 절반 지점에 해당하는 위치를 의미한다.

 

즉, 인구의 합을 2로 나눈 값에 해당하는 누적 인구를 찾아서 그 위치를 결정하면 된다.

 

<소스코드>

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;
using ll = long long;

int n;
vector <pair<int, int>> vec;

int main() 
{
    int i, j;
    scanf("%d", &n);
    ll ans = 0;
    for(i=0;i<n;i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        vec.push_back({x, y});
        ans += y;
    }
    sort(vec.begin(), vec.end());
    ll res;
    if(ans % 2) {
        res = (ans + 1) / 2;
    }
    else {
        res = ans / 2;
    }
    ll now = 0;
    for(i=0;i<n;i++) {
        now += vec[i].second;
        if(now >= res) {
            printf("%d", vec[i].first);
            return 0;
        }
    }
    return 0;
}

 

처음에는 거리를 생각안해서 반례가 생긴줄알고, 해당 지점에 우체국을 세웠을 때 우체국과 모든 사람들의 거리의 합을 구했었는데 longlong으로도 overflow가 떠서 다른 방법을 이용해서 풀었다.