[백준 17435] 합성함수와 쿼리 (파이썬 / Python)

---

📑 문제

문제링크 : 합성함수와 쿼리

---

🤔 생각의 흐름

얼마 전에 알게된 희소 배열 알고리즘을 써야겠다고 생각했습니다. ‘희소 배열이 뭐지?’ 하시는 분들은 이 글을 보고 와주세요.

---

🎯 풀이방법

희소 배열 문제이며, 시간복잡도는 $O((m + Q) \log N)$ 입니다.

move[i][j] : j 번 노드가 $2^i$ 번 이동했을 때의 위치

1. 희소 배열 알고리즘을 위한 전처리를 해줍니다.

2. 입력받은 쿼리를 전처리한 리스트를 이용하여 구합니다.

---

🔎 유의할 점

• 희소 배열 알고리즘을 이해하고 푼다면 크게 유의할 점은 없습니다.

---

💻 코드

from sys import stdin

input = stdin.readline


def solve():
    m = int(input())

    # log2(500_000) + 1 = 19
    length = 19

    # move[i][j]: f_2^i(j)
    move = [[0] * (m + 1) for _ in range(length)]
    move[0][1:m+1] = [*map(int, input().split())]

    for i in range(1, length):
        for j in range(1, m + 1):
            move[i][j] = move[i-1][move[i-1][j]]

    Q = int(input())
    for _ in range(Q):
        n, x = map(int, input().split())
        idx = 0
        while (1 << idx) <= n:
            if n & (1 << idx):
                x = move[idx][x]
            idx += 1
        print(x)


if __name__ == '__main__':
    solve()