[C++] 합성함수와 쿼리 (백준 17435번)

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

 

이 문제를 풀기 위해 x번 정점에서 n번 움직인 후의 정점을 구하는 행동을 빠르게 처리해야 한다.

이를 위해 x번 정점에서 2^k번 움직인 후의 정점을 미리 구해놓으면, 하나의 쿼리가 들어왔을 때 n을 이진수의 형태로 생각하여 전처리 해둔 값들만을 사용하여 쿼리에 대한 답을 구할 수 있다.

이런 식으로 쿼리를 빨리 처리하기 위해 2의 제곱수 단위의 값들을 미리 구해놔서 전처리 해두는 것을 sparse table이라고 한다고 한다.

(보통 상태 전이 등에서는 binary lifting이라고 하고, 구간 쿼리 등에서는 sparse table이라고 부르는 것 같다.)

 

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

void solve() {
    int m;
    cin >> m;

    // sp[i][j]: i번 정점에서 2^j번 이동한 정점
    vector<vector<int>> sp(m + 1, vector<int>(20));
    for (int i = 1; i < m + 1; i++) cin >> sp[i][0];

    for (int j = 1; j < 20; j++) {
        for (int i = 1; i < m + 1; i++) {
            sp[i][j] = sp[sp[i][j - 1]][j - 1];
        }
    }

    int q;
    cin >> q;

    while (q--) {
        int n, x;
        cin >> n >> x;
        int cur = x;
        for (int j = 0; j < 20; j++) {
            if (n & (1 << j)) cur = sp[cur][j];
        }
        cout << cur << '\n';
    }
}

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

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

(AC)