[백준] 17435. 합성함수와 쿼리

 

풀이.

sparse table이라는 자료구조를 이용해야한다.

sparse table은 정적 구간 질의를 처리할 수 있는 자료구조인데 대부분의 구간 질의를 O(log n)시간에 처리하지만 특정한 연산에 대해서는 O(1)의 시간 복잡도를 가지는 특징을 가지고 있다.

sparse table로 구간 질의를 처리하기 위해서는 배열이 정적이어야한다.

 

해당 문제를 살펴보면 f2(1) = f(f(1)), f4(1) = f2(f2(1))과 같은 구조로 되어있다.

즉 sparse table에는 2의 제곱으로 늘어나는 값들을 저장해서 풀면된다.

 

아직 확실히 이해가 되지 않아서 다시 풀어보아야 할 것 같다.

 

 

소스코드.

 

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

view raw 17435 - 합성함수와 쿼리.py hosted with ❤ by GitHub