문제 링크 : 백준 2141번
그리디 알고리즘을 이용해야 할 것 같은데 방법이 도저히 생각이 안나서 다른 풀이를 참고했다.
각 사람들까지 거리의 합이 최소가 되려면 우체국을 설치하는 위치 기준으로 양쪽에 있는 인구가 비슷해야한다.
⭐️ 이분 탐색으로도 풀 수 있는 것 같다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector<pair<long long, long long> > arr;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
long long total=0;
for(int i=0 ; i<n ; i++) {
long long x,a;
cin >> x >> a;
arr.push_back(make_pair(x, a));
total += a;
}
sort(arr.begin(), arr.end());
long long temp=0;
for(int i=0 ; i<n ; i++) {
temp += arr[i].second;
if(temp>=(total+1)/2) { // 인구 밀집도의 중간 => 각 사람들까지 거리의 합이 최소가 되는 위치
cout << arr[i].first << "\n";
break;
}
}
return 0;
}