[BOJ 2141, 어려움] 우체국 (C++)

예전에 힘들게 풀었던 문제인데 다시봐도 모르겠어서 다시풀어보았다

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

 

1. 관찰하기

N이 10만이기 때문에 N*N으론 풀 수 없고 NlogN이하로 풀릴거같다

주어지는 값의 범위가 매우 크기 때문에 오버플로우에 주의해야 할지도 모르겠고

배열을 이용해 값들을 저장할 수 없을 것 같다 -> map,set을 써야될거같다

 

이거는 처음 읽을 땐 잘 모르겠는데

답을 알고 보면 이해가 좀 된다

각 마을까지의 거리의 합을 구하는 문제면 모든 마을에 사는 사람 수를 1로 놓고 계산하는 것과 같다

 

정답이 여러 개 존재할 수 있다는 것도 힌트다. 우체국을 어디 놓는지에 따라 계산값이 어떻게 되는지 따져보자

 

2. 케이스 따져보기

먼저 예제를 보자

일단 마을이 1과 2와 3위치에 있으니 1과 3사이 범위에 정답이 존재함은 자명하고 2가 답인 건 매우 그럴듯하게 보임

 

그럼 위의 예제에서 마을사이의 거리를 더 늘려보면 어떻게 될까

따져보니 계산값은 극소값이 존재하고 그 근처에서 정답이 존재함. 값을 바꿔서 다시 해보면,

역시 극소값이 존재하고 그 근처에서 정답이 존재함.

 

이만큼 따져보니 어느정도 예상이 된다

1. 기울기가 변하는 점은 결국 마을 위치이기 때문에, 모든 범위를 다 따져볼 필요 없이 마을만 따져보면 됨

2. 답이 여러 개 존재할 수 있다는 건

이런 모양으로 극값이 존재하는 경우이고 역시 모든 범위 따질 필요 없이 마을 위치에서만 따지면 됨

결국 문제에서 최소값이 발생하는 지점을 찾기를 요구한다는 점에서

대학에서 잠깐 배웠던 경사하강법 이런게 생각나기도 한다

 

3. 전략 세우기

그래서 어떻게 푸냐??

일단 우체국을 모든 마을에 세워보면서 계산값을 일일히 구해보는 일은 N*N이기 때문에 할 수 없다

그래서 그리디한 접근을 해야 하는데....

정답코드: 안보는걸 추천

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;

int main()
{
    fastio;
    int N;cin>>N;
    map<ll,ll> mm;
    ll total = 0;
    ll cur = 0;
    for (int i = 0; i < N; i++)
    {
        ll a,b;cin>>a>>b;
        mm[a]+=b;
        total+=b;
    }
    
    for (auto [a,b]:mm)
    {
        cur+=b;
        if(cur>=(total+1)/2){
            cout<<a;
            return 0;
        }
    }
    return 0;
}

 

계산값을 한번도 계산해볼 필요 없이, 마을에 사는 사람 수만 따져봐도 답을 구할 수 있다

위에서 그래프 기울기는 결국

우체국 왼쪽에 있는 사람 수 vs 오른쪽에 있는 사람 수 에 의해 결정되기 때문이다

순회하면서 우체국 왼쪽에 있는 사람 수를 더해나가다가

왼쪽에 있는 사람 수가 총 사람의 절반 이상이 되는 그 마을에 우체국을 세워버리면 거기가 답임

위에서 생각해본 이런 경우도 위 코드로 커버가 된다

예제를 생각해보기 어렵지 않으니 직접 돌려보길 바란다

 

4. 총평

수학적 직관이 중요한 문제 같다

수학 놓은지 오래될수록(나) 직관이 딸려서 고생할 것 같다

정보올림피아드 뛰는 사람들은 문제 보자마자 머리속에 그래프 떠오르고 왼쪽오른쪽 사람수에 의해 기울기 달라진다 생각하고 코드 1분만에 작성해서 제출할듯

정답까지 가는 길은 오래걸렸지만 코드만 보면 짱간단해서 골드4인가보다