[Python]최소공통조상 백준 17435

   문제

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

sparsetable을 이용한 문제이다.

http://www.secmem.org/blog/2019/03/27/fast-LCA-with-sparsetable/

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220793361738

두 사이트를 읽어보면 이해하기 편하다.

i=시작노드

k=연산횟수

라고 생각했을때

f^4(3)=f(f(f(f(3))))이다.

5
3 3 5 4 3
5
1 1
2 1
11 3
1000 4
5 1

문제의 예제를 살펴보자.

f^2(1)=5 이다.

f^4(1)=5 이다.

f^4(1)=f^2(5)와 같다.

이 원리를 이용하면 

f^2(5)=5 이다.

f^8(1)=?

f^8(1)=f^4(f^4(1)) 이다.

이렇게 DP를 이용하여 값을 저장해주면 O(MlogM)만의 시간복잡도를 가지고 희소 

테이블을 완성할수있다.

이런식으로 연산을 배로 늘려가며 저장해주면 각 쿼리마다 O(1)에 처리할수 있게된다.

이런 값들을 저장하는 공간복잡도는 MlogM만큼이 필요하다.

희소 테이블(sparse table)은 이렇듯 모든 값을 저장하는 것이 아니라 몇몇의 계산값을 

통해  계산을 효율적으로 만들어주는 방법이다.

import sys
m=int(sys.stdin.readline())
f=[0]+list(map(int,sys.stdin.readline().split()))
#1<m<=200000 logm=17.609...
DP=[[f[i]] for i in range(m+1)]
for j in range(1,19):
    for i in range(1,m+1):
        DP[i].append(DP[DP[i][j-1]][j-1])
 
Q=int(sys.stdin.readline())
for _ in range(Q):
    n,x=map(int,sys.stdin.readline().split())
    for j in range(18, -1, -1):
        if n >= 1<<j:#2^j보다 크다면
            n -= 1<<j#2^j을 빼주고 나머지를 계산해준다.
            x = DP[x][j]#0이 될때까지 반복
    print(x)
 

pypy3를 통해 통과할수있었다.

동적 import를 통해 입력을 받는부분을 조금 수정하면 python3으로도 통과는 가능하다.

https://brownbears.tistory.com/134

input = __import__('sys').stdin.readline
m=int(input())
f=[0]+list(map(int,input().split()))
#1<m<=200000 logm=17.609...
DP=[[f[i]] for i in range(m+1)]
for j in range(1,19):
    for i in range(1,m+1):
        DP[i].append(DP[DP[i][j-1]][j-1])
 
Q=int(input())
for _ in range(Q):
    n,x=map(int,input().split())
    for j in range(18, -1, -1):
        if n >= 1<<j:#2^j보다 크다면
            n -= 1<<j#2^j을 빼주고 나머지를 계산해준다.
            x = DP[x][j]#0이 될때까지 반복
    print(x)