백준 3770번 대한민국 - C++(cpp) 풀이 + 그림 설명

 1615번 문제와 똑같고, 대신 테스트 케이스가 여러 개 주어지는 문제이다. 1615번은 Swift로는 시간 초과가 나서 못 풀었어서 이 문제도 그냥 C++로 도전.

 

 서쪽을 기준으로 작은 수부터 차례로 동쪽과 연결해준다. 1, 2가 연결 완료된 상태이고, 이제 서쪽의 3번에 2개의 고속도로(3-2와 3-5)를 설치해야 하는 상황이라고 하자.

 

 

 3-2로 가는 고속도로 먼저 설치해야 하는데(이유는 나중에), 이 고속도로를 설치할 때 생기는 교차점의 개수는 동쪽에서 2 초과인 곳 [3, 4, 5]에 연결된 고속도로 개수의 합과 같다. 이미 존재하는(검은색) 고속도로들은 전부 서쪽에서는 3(빨간 선의 시작점)보다 위에 있다. 따라서 방금 설치한 빨간색 고속도로와 교차하려면 동쪽에서는 2(빨간 선의 도착점)보다 아래 있어야 한다.

 

 

 이제 3-5도 연결해주자. 3-5 고속도로와 교차하려면 동쪽의 5번 초과인 이상인 곳에 연결되어 있어야 할 텐데, 없으므로 0이다. 만약에 3-5부터 연결했으면 3-2를 연결할 때 3-5와도 교차하는 것으로 잘못 카운트하게 된다. 따라서 출발점이 같으면 도착점이 더 작은 것부터 연결해주어야 한다. 이렇게 고속도로(간선)들을 정렬한 뒤, [도착점+1...]의 구간합을 구해주고, 동쪽에 연결된 고속도로를 업데이트해주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct FenwickTree {
    vector<int> tree;

    FenwickTree(int n) : tree(n+1) {};

    int sum(int pos) {
        int ret = 0;
        while (pos > 0) {
            ret += tree[pos];
            pos &= (pos - 1);
        }

        return ret;
    }

    void add(int pos, int val) {
        while (pos < tree.size()) {
            tree[pos] += val;
            pos += (pos & -pos);
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int testcase;
    cin >> testcase;

    for (int t = 1; t <= testcase; t++) {
        vector<pair<int, int>> edges;

        int N, M, K;
        cin >> N >> M >> K;

        FenwickTree fwt(1001);

        for (int i = 0; i < K; i++) {
            int s, e;
            cin >> s >> e;
            edges.push_back({s, e});
        }

        sort(edges.begin(), edges.end());

        long long result = 0;
        for (int i = 0; i < K; i++) {
            if (edges[i].second != M) {
                result += fwt.sum(M - edges[i].second);
            }
            fwt.add(M + 1 - edges[i].second, 1);
        }
        cout << "Test case " << t << ": " << result << "\n";
    }

    return 0;
}