백준 17435번: 합성함수와 쿼리 (Python)

접근

sparse table 을 이용하는 문제이다. sparse table 은 모든 계산값을 저장하는 것이 아니라 배로 늘어나는 연산의 값을 저장해줌으로써 문제가 주어졌을 때 그 계산을 편리하게 해줄 수 있는 표를 만드는 것이다.

문제의 예시에서 f(1) = 3 의 값을 가지고 f2(1) = f(f(1)) = f(3) = 5 의 값을 가지게 된다.
f4(1) 의 경우, f2(f2(1)) 와 같이 이전 단계에 구했던 f2 의 값들을 이용하여 빠르게 구할 수 있고, 이와 같이 2의 제곱으로 늘어나는 값들을 저장해주게 된다. 이 표를 이용하여 쿼리에 주어진 fn(x) 의 값을 빠르게 구할 수 있다.

코드

import sys

m = int(sys.stdin.readline())
f = [0] + list(map(int, sys.stdin.readline().split()))
dp = [[f[i]] for i in range(m + 1)]
for j in range(1, 19):
    for i in range(1, m + 1):
        dp[i].append(dp[dp[i][j - 1]][j - 1])
q = int(sys.stdin.readline())
for _ in range(q):
    n, x = map(int, sys.stdin.readline().split())
    for j in range(18, -1, -1):
        if n >= 1 << j:
            n -= 1 << j
            x = dp[x][j]
    print(x)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!