[동적 계획법] 피보나치 함수

백 트래킹이 마무리가 되고 동적 계획법으로 넘어왔다.

 

동적 계획법 자체는 거창한 내용은 없었고, 값을 재활용한다는 핵심 개념만 알고 가면 될 것 같다.

값을 저장하고 꺼내오는 과정에서의 최적화에 대한 고민이 중요할 것 같다.

 

1003번: 피보나치 함수

from sys import stdin

T = int(stdin.readline())

f_arr = [-1] * 41
f_arr[0] = [1, 0]
f_arr[1] = [0, 1]


def f(n: int):
    global f_arr
    if f_arr[n] != -1:
        return f_arr[n]
    else:
        [z1, o1] = f(n - 1)
        [z2, o2] = f(n - 2)
        fn = [z1 + z2, o1 + o2]
        f_arr[n] = fn
        return fn


for _ in range(T):
    print(" ".join(map(str, f(int(stdin.readline())))))