[백준] 2141 - 우체국

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

2141번: 우체국

 

python은 모르겠지만, cpp로 누적합을 이용해 각 지역마다 모든 누적합을 구해준다면 long long overflow가 나게 된다.

10억 * 10억 * 10만.

 

그래서 다른 전략을 취하였다.

거리를 신경 쓰지 않으려면, 사람의 수 만으로 해결해야 한다.

 

잘 생각해보면, 단순히 해당 마을을 기준으로 왼쪽과 오른쪽의 위치해 있는 마을들의 사람 수의 합을 최소로 하게 하면 된다.

따라서 마을 위치 순으로 정렬해준 다음 하나씩 더해가며 답을 구하였다.

 

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

int n;
pair<long long, long long> arr[100001];
long long sum;

int main() {

	cin >> n;

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

	sort(arr + 1, arr + 1 + n);

	long long ans = 0;

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