백준 / python / 17435. 합성함수와 쿼리

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

 

문제 요약

1. m 개의 숫자가 주어진다.
2. m 개의 숫자가 각각 $f(1), f(2), \cdots , f(m)$ 일 때, $f_n(x)$ 를 구하라

 

 

풀이 요약

1. 한 번씩 뛰어 A -> B -> C 라면 두 번씩 뛰어 A->C 이다.
2. 이걸 $2^i$ 만큼 이동한 경우를 미리 저장해둔다.
3. n 에 $2^i$ 이 포함되어있다면  현재 위치에서 $2^i$ 번 뛴 곳으로 이동하는 것을 $n_{(2)}$ 의 자릿수만큼 반복한다.

 

주의사항

이 알고리즘은 Sparse Table 을 사용하는 문제이다.

풀이 시간이 나보다 많이 빠른 풀이도 많으니 그 풀이들을 참조하면 좋겠다.

조건문이 많다고 빨라지진 않는다. 오히려 조건문을 위해 반복문이 포함된다면 성능이 나빠진다.

예를 들면 get 함수의 while 문이 없는 것이 낫다.

while 문 대신 이때까지 갱신한 dp 의 줄 수와 i 값을 비교하여 그 차이만큼 dp 줄 수를 추가하면 빠를 것이다.

한 번 해보겠다.

while 문 자체가 없어지진 않았지만, 이미 알고 있는 index 값들에 대한 반복이 없어져서 훨씬 빨라졌다.

# 수정전 코드

from sys import stdin

input = stdin.readline
ans = []

M = int(input())
dp = [[0] * (M + 1) for _ in range(19)]
dp[0] = [0] + list(map(int, input().split()))


# dp[i][x] 를 반환하는 함수
def get(i, x):
    if dp[i][x]:
        return dp[i][x]

    index = 0
    while i > index:
        if not dp[index + 1][x]:
            dp[index + 1][x] = get(index, get(index, x))
        index += 1

    return dp[index][x]


# f_n(x) 를 반환하는 함수
def solve(n, x):
    i = 0
    ans = x
    while n >= (1 << i):
        if n & (1 << i):
            ans = get(i, ans)
        i += 1
    return ans


Q = int(input())

for q in range(Q):
    n, x = map(int, input().split())
    print(solve(n, x))

# 수정 후 코드

from sys import stdin

input = stdin.readline
ans = []

M = int(input())
dp = [[0, *map(int, input().split())]]


# dp[i][x] 를 반환하는 함수
def get(i, x):
    if len(dp) > i:
        return dp[i][x]

    while i >= len(dp):
        dp.append([dp[-1][x] for x in dp[-1]])

    return dp[i][x]


# f_n(x) 를 반환하는 함수
def solve(n, x):
    i = 0
    ans = x
    while n >= (1 << i):
        if n & (1 << i):
            ans = get(i, ans)
        i += 1
    return ans


Q = int(input())

for q in range(Q):
    n, x = map(int, input().split())
    print(solve(n, x))