백준[17435] 합성함수와 쿼리

문제 설명

문제 링크

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

17435번: 합성함수와 쿼리

풀이

sparse table이라는 자료구조를 이용하여 풀이할 수 있다.

sparse table은 https://namnamseo.tistory.com/entry/Sparse-Table 이 자료를 보고 공부했다.

sparse table을 이용하여 2^k만큼 합성하였을 때의 값을 미리 구해놓는다면 쿼리당 log 시간 복잡도에 계산할 수 있다.

예를 들어) 7번 합성한 것을 구한다면 1 -> 2 -> 4로 움직이면 된다.

코드

#include <cstdio>
#include <cmath>

int table[20][500005];

int main() {
    int m; scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &table[0][i]);
    }
    for (int k = 1; k < log2(500000) + 1; k++) {
        for (int i = 0; i <= m; i++) {
            int tmp = table[k - 1][i];
            table[k][i] = table[k - 1][tmp];
        }
    }
    int q; scanf("%d", &q);
    while (q--) {
        int n, x; scanf("%d %d", &n, &x);
        for (int i = 0; n; i++) {
        //ex) 7 -> 0111 이므로 1 -> 2 -> 4칸씩 움직임
            if (n & 1) x = table[i][x];
            n >>= 1;
        }
        printf("%d\n", x);
    }
}