[희소 테이블/파이썬] 백준 3117번 : YouTube / 플래5

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

3117번: YouTube

import sys
input = sys.stdin.readline
n, k, m = map(int, input().split())
lst = list(map(int, input().split()))
next = list(map(int, input().split()))

h = 1
count = 0
while h <= m:
    h = h<<1
    count += 1

table = [[0 for _ in range(k+1)] for _ in range(count+1)]
table[0] = [x for x in range(k+1)]

for j in range(1, k+1):
    table[1][j] = next[j-1]

for i in range(2, len(table)):
    for j in range(1, k+1):
        a = table[i-1][j]
        table[i][j] = table[i-1][a]

answer = []
for i in range(len(lst)):
    cur = lst[i]
    j = m - 1
    while j > 0:
        last_bit = j & -j
        cur = table[len(bin(last_bit))-2][cur]
        j -= last_bit
    answer.append(cur)
print(*answer)

m값이 최대 10억으로 매우 크다.

희소 테이블(spars table)을 활용해야 시간안에 풀 수 있다.

table[i][j]값은 j번째에서 시작해서 2**(i-1)분 후의 위치를 가지고 있다. 

ex) m = 7일 경우, 이진수 표현으로 111(2)이다.

j = 111(2)라 하면 j&-j = 1(2)가 제일 마지막 1비트의 자리를 알려주기때문에 이 값을 이용하여 테이블을 옮겨다니며 값을 빠르게 찾으면 된다.