[BOJ/C++] 2141: 우체국

🏅 Gold 4

✏️ 최종 솔루션

⭐️ Greedy + 이분탐색
⭐️ 마을 개수를 대상으로 탐색
❗️ 마을간의 거리는 고려하지 않기 때문에 첫번째 마을부터 현재 마을까지 누적된 사람과 현재 마을 이후부터 마지막 마을부터 누적된 사람이 균형을 이루는 지점을 탐색하는 것이 관건

1. 마을 인덱스 순으로 오름차순 정렬
2. 첫번째 마을부터 각 마을까지 누적된 사람 count
   ❗️ 현재 마을의 사람도 포함해야 함
3. left = 0, right = n-1 로 설정하여 이분탐색
4. mid 인덱스에서 왼쪽의 사람 누적과 오른쪽의 사람 누적을 비교해서 더 큰 방향으로 이어서 탐색 ➡️ 인덱스를 옮겨서 양측의 균형을 찾아야 하기 때문

📌 self feedback

Greedy 유형에 속아서 이분탐색을 생각하지 못했다
항상 탐색값 저장을 하는 것은 최소값을 구하는 것이면 최소값 탐색하는 방향에, 최대값을 구하는 것이라면 최대값 탐색하는 방향에서 저장해야 함

✏️ 최종 code

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

int main() {
    long long n;
    cin >> n;
    vector<pair<int,int>> town;
    vector<long long> sum(n,0);
    for(int i=0;i<n;i++) {
        int x,a;
        cin >> x >> a;
        town.push_back({x,a});
    }
    
    sort(town.begin(),town.end());
    
    sum[0]=town[0].second;
    for(long long i=1;i<n;i++) {
        sum[i]=sum[i-1]+town[i].second;
    }
    
    int left=0, right=n-1, ans=1000000001;
    while (left<=right) {
        int mid=(left+right)/2;
        
        // 왼쪽이 더 크면 왼쪽으로 이동
        if(sum[mid]>=sum[n-1]-sum[mid]) {
            right=mid-1;
            ans=min(ans,town[mid].first);
        }
        else {
            left=mid+1;
        }
    }
    
    cout << ans << endl;
    
}