백준 17435 <합성함수와 쿼리> Python

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

17435번: 합성함수와 쿼리

---

희소 배열에 관한 기본문제입니다. 기본적으로 희소 배열이란 어떤 구조를 탐색할 때 탐색 시간을 줄이기 위한 방법으로, 2^n 에 대한 정보를 미리 기록해놓고 이를 더 작은 2^m 으로 쪼개어 탐색합니다.

이 문제에서는 f(x) 를 중첩시키는 형태로 사용하게 되는데, f(x) 를 7번 중첩시킨다고 가정하겠습니다.

7 은 2진수로 표현하면 111 이므로 2^2 + 2^1 + 2^0 입니다. 즉 f_2^0( f_2^1( f_2^2(x) ) ), f(f_2(f_4(x))) 를 구해주면 됩니다. 우리는 테이블로 미리 이 정보들을 구해놨으므로 순서대로 값을 넣어주기만 하면 됩니다.

---

import sys

from math import log2

def solution(m, function_list, Q, data_list):

    # 희소 배열 행 길이

    column_len = int(log2(500000))+1

    # 희소 배열

    sparse_table = [[0] + function_list for _ in range(column_len)]

    # 희소 배열 채우기, sparse_table[i][j] = f_2^i(j)

    for j in range(1, column_len):

        for i in range(1, len(sparse_table[j])):

            sparse_table[j][i] = sparse_table[j-1][sparse_table[j-1][i]]

    # 데이터 리스트를 순회

    for n, x in data_list:

    # n 을 2의 지수로 분해

        n_bin = list(bin(n)[2:])

        # 2진수 길이

        n_len = len(n_bin)

        # 2진수를 순회하며 함수 적용

        for idx in range(n_len):

            # 2진수의 값이 1이면

            if int(n_bin[idx]):

                # x = 함숫값

                x = sparse_table[n_len-1-idx][x]

        print(x)

m = int(sys.stdin.readline())

function_list = list(map(int, sys.stdin.readline().split()))

Q = int(sys.stdin.readline())

data_list = [list(map(int, input().strip().split())) for _ in range(Q)]

solution(m, function_list, Q, data_list)