[백준] 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의 제곱으로 늘어나는 값들을 저장해서 풀면된다.

 

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

 

 

소스코드.