[ICPC] 백준 3770 - 대한민국

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

 

문제 분석

문제의 예시를 도식화한 그림

두 고속도로가 하나의 교차점을 만들수 있을 때(세 개 이상의 고속도로가 만나면 안된다.) 교차점의 개수를 구하는 문제이다.

 

서쪽의 정점들을 pivot으로 하여 오름차순 정렬하면 다음과 같이 그릴 수 있다.

 

 

여기서 동쪽의 정점을 index, 서쪽으로 연결된 정점을 value라고 하자.

 

그렇다면 어떤 index의 value가 1 ~ index - 1 범위의 value와 비교했을 때 index의 value가 더 작다면 교차한다는 사실을 관찰할 수 있다.

 

이는 어떤 index의 value가 index + 1 ~ end 범위의 value와 비교했을 때 index의 value가 더 크다면 교차한다는 것과 동치가 된다.

 

하나의 교차점은 오직 두개의 고속도로가 만나서 생긴다고 했으므로 중간에 존재하는 다른 고속도로는 영향을 받지 않는다는 것도 유의하자.

 

이를 통해 i + 1 ~ end에서 A[i]보다 큰 수의 갯수를 구하는 문제 즉, inversion counting으로 이해할 수 있다.

구현

이 게시글에서는 펜윅 트리를 사용하여 문제를 해결했다.

 

도로가 최대 40만 개 주어지므로 주어진 두 정점을 pair로 하여 배열이나 벡터같은 선형 자료구조에 담아준다. 그리고 오름차순 정렬하여 같은 정점에 이어진 도로가 서로를 교차하지 않도록 한다. 어느 쪽을 기준으로 정렬할지는 상관 없다.

 

정렬 기준으로 쓰이지 않은 나머지 정점을 value로 하여금 inversion counting을 해주면 문제를 해결할 수 있다.

 

전체 코드 - 펜윅 트리

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int t, n, m, k;

ll fenwick[1001];

void add(int idx, int val)
{
    while (idx <= 1000)
    {
        fenwick[idx] += val;
        idx += (idx & -idx);
    }
}

ll sum(int idx)
{
    ll res = 0;

    while (idx > 0)
    {
        res += fenwick[idx];
        idx &= (idx - 1);
    }

    return res;
}

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

    cin >> t;
    
    int num = 1;

    while (t--)
    {
        memset(fenwick, 0, sizeof fenwick);
        ll ret = 0;
        cin >> n >> m >> k;

        vector<pii> highway(k);

        for (int i = 0; i < k; ++i)
            cin >> highway[i].first >> highway[i].second;
        
        sort(highway.begin(), highway.end());

        for (int i = k - 1; i >= 0; --i)
        {
            ret += sum(highway[i].second - 1);
            add(highway[i].second, 1);
        }

        cout << "Test case " << num++ << ": " << ret << '\n';
    }
}