[백준-2285] 우체국

그리디 알고리즘

을 사용하는 문제였다.

일단 시간제한이 2초인데, 입력값이 (위치, 인구수) 쌍으로 10만개이다. 이를 일반적인 브루트포스로 풀게되면 전체 평균을 구하는 과정 중에 값의 범위 때문에 터질 수도 있다. 다만 시간으로는 안 터지지 않을까 싶다.

즉, 이 문제의 경우 그리디하게 위치를 정해주어야 하는데 그 로직은 다음과 같다.

1. 입력받은 쌍을 위치 순으로 정렬한다.
2. 해당 위치까지의 누적합을 배열에 저장해둔다.
3. 그 후 이분탐색으로 왼쪽 누적합, 오른쪽 누적합의 차이가 최소인 지점을 찾는다.

생각보다 간단한 로직이다. 허나 평균을 구하는게 아닌 누적합 자체로 이분탐색을 한다는 것 자체가 생각하기 어렵기 때문에 경험이 필요한 문제라 생각한다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>


using namespace std;
typedef long long LL;

LL x[100001];
LL a[100001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	vector<pair<LL, LL>> v;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> a[i];
		v.push_back({ x[i], a[i] });
	}
	sort(v.begin(), v.end());

	vector<LL> sum;
	sum.push_back(v[0].second);
	for (int i = 1; i < n; i++) {
		sum.push_back(sum[i - 1] + v[i].second);
	}

	LL left = 0, right = n, mid;
	LL pos = 100000;
	while (left <= right) {
		mid = (left + right) / 2;
		if (sum[mid] < sum[n - 1] - sum[mid]) {
			left = mid + 1;
		}
		else if (sum[mid] > sum[n - 1] - sum[mid]) {
			right = mid - 1;
			pos = min(pos, v[mid].first);
		}
	}
	cout << pos;
	return 0;
}

 

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

2285번: 우체국