백준 2141 우체국 (C++)

https://www.acmicpc.net/problem/2141

#include <iostream>
#include <vector>
#include <algorithm>

#define ll long long

using namespace std;


vector<pair<ll, ll>> arr;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    ll n;
    int ans;
    cin >> n;


    ll sum = 0;

    arr.resize(n);

    for (ll i = 0; i < n; i++) {
        cin >> arr[i].first >> arr[i].second;
        sum += arr[i].second;
    }

    sort(arr.begin(), arr.end());

    ll temp = 0;
    for (int i = 0; i < n; i++) {
        temp += arr[i].second;
        if (temp >= (double)sum / 2) {
            ans = arr[i].first;
            break;
        }
    }


    cout << ans;


    return 0;
}

1. 문제

n개의 마을의 번호와 사람 수가 주어진다. i번째 마을은 x[i]에 있으며, 해당 마을의 사람 수가 같이 주어진다. 이 마을 중 한 마을에 우체국을 세우려 하는데, 우체국에서 각 사람까지의 거리는 최소가 되어야 한다. 이 때, 우체국이 있어야 할 위치를 출력하라.

2. 풀이

 일직선 상에서 존재하는 마을들에서 사람들을 기준으로 최단 거리에 위치한 우체국을 세우려면 해당 일직선에 마을 사람들을 일렬로 세우고, 우체국은 최대한 중간에 위치해야 한다.

    ll sum = 0;

    for (ll i = 0; i < n; i++) {
        cin >> arr[i].first >> arr[i].second;
        sum += arr[i].second;
    }
    
    sort(arr.begin(), arr.end());

우선 마을의 총 인원 수를 구하기 위해 입력받을 때 사람 수를 저장한다. 그 후, 일직선에 사람들을 줄 세우기 위해 마을의 번호를 기준으로 정렬한다.

    ll temp = 0;
    for (int i = 0; i < n; i++) {
        temp += arr[i].second;
        if (temp >= (double)sum / 2) {
            ans = arr[i].first;
            break;
        }
    }

각 마을을 돌아가면서 현재까지의 마을 사람의 합을 구한다. 이 값이 마을의 총 인원 수의 절반을 넘어가면 그 위치가 중간값이므로 해당 위치에 우체국을 세운다. 해당 위치의 마을 번호를 출력하면 정답을 구할 수 있다.