[C++] 2141번: 우체국

링크

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

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 이며 모든 입력은 정수이다.

출력

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

예제 입력 1 복사

3
1 3
2 5
3 3

예제 출력 1 복사

2

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <stack>

using namespace std;

int main(void)
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	vector<pair<long long, long long>> vil;
	long long sum = 0;
	int n; 
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		long long temp_1;
		long long temp_2;
		cin >> temp_1 >> temp_2;
		vil.push_back({ temp_1, temp_2 });
		sum += temp_2;
	}
	sort(vil.begin(), vil.end());

	long long current = 0;
	for (int i = 0; i < n; i++)
	{
		current += vil[i].second;
		if (current >= (sum + 1) / 2)
		{
			cout << vil[i].first;
			return 0;
		}
	}
	return 0;
}

풀이

• 그리디 알고리즘으로 풀었다.
  
  
• 마을 번호 입력이 순서대로 들어오는것이 아니다.
  따라서 정렬 없이 진행 시 마을 순서가 뒤죽박죽이 되므로 sort를 이용해 정렬 해 준다.
• 모든 마을의 총 인원의 절반(홀수의 경우 +1)을 구하고, 마을별로 차례대로 인원을 더해
  앞서 구한 인원을 넘어서게 되면 해당 마을이 거리합이 최소가 되는 마을이다.