문제

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

풀이

그리디

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

int main() {
  	ios::sync_with_stdio(0);
  	cin.tie(0);

	int N; 
	cin >> N; 

	vector<pii> v; 
	ll sum = 0; 
	
	for(int i = 0; i < N; i++){
		int pos, num; 
		cin >> pos >> num; 
		v.push_back({pos, num});
		sum += num;
	}

	// 마을 위치를 기준으로 정렬 
	sort(v.begin(), v.end()); 

	ll temp = 0; 
	for(int i = 0; i < N; i++){
		temp += v[i].second;

		// 우체국의 좌우 사람 수가 최대한 비슷해지는 위치에 설치 
		if(temp >= (sum + 1) / 2) {
			cout << v[i].first; 
			break; 
		}
	}
	
  	return 0;
}

누적합 & 이분탐색

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll; 

int N; // 최대 10만 
vector<pii> arr;  // { 마을 위치, 사람 수 } 
vector<ll> psum; // 사람 수의 누적 합 (좌표가 최대 10만이므로 그 합은 ll 타입)

int binarySearch() {
	// 우체국 위치의 최솟값, 최댓값 설정 
	int left = 0; 
	int right = N - 1; 
    
    // 각 사람까지의 거리 합이 최소가 되는 우체국 위치 
	int ans = 1e9; 
	
	while(left <= right){
		int mid = (left + right) / 2; 

		// 사람 수를 구하기 위해 누적합 배열 이용 (시간 복잡도 단축) 
		ll leftPeople = psum[mid]; 
		ll rightPeople = psum[N - 1] - psum[mid]; 
		
        // 우체국 좌우의 사람 수가 최대한 비슷해지는 위치를 이분탐색 
		if(leftPeople >= rightPeople){ 
			right = mid - 1;
            
            // 가능한 위치가 여러 개인 경우, 더 작은 값을 정답으로 저장 
			ans = min(ans, arr[mid].first);
		}else{
			left = mid + 1;
		}
	}

	return ans; 
}

int main() {
  	ios::sync_with_stdio(0);
  	cin.tie(0);

	cin >> N; 

	for(int i = 0; i < N; i++){
		int pos, num; 
		cin >> pos >> num; 
		arr.push_back({pos, num}); 
	}

	// 마을의 위치를 기준으로 정렬 
	sort(arr.begin(), arr.end()); 

	// 사람 수의 누적 합 구하기 
	psum.push_back(arr[0].second);
	
	for(int i = 1; i < arr.size(); i++){
		psum.push_back(psum[i - 1] + arr[i].second); 
	}
    
	cout << binarySearch();
	
  	return 0;
}

이분탐색을 이용한 방법이 실행 시간과 메모리 사용량 측면에서 조금 더 비효율적이다.

그런데 이 문제를 직관적으로 이해하고 그리디로 해결할 수 있는 방법을 찾아내는 것이 쉽지 않은 거 같다.