[Python]동적계획법 백준 2748

   문제

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

이전 피보나치 수열은 재귀를 활용해 푼것으로 기억이난다. 

이번에는 동적계획법(Dynamic Programming)을 활용한 방법이다.

동적계획법은 특정 범위 까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하

여 효율적으로 값을 구하는 알고리즘 설계기법이다.

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95

밑에 보면  재귀를 이용한 방법과 동적계획법을 이용했을때의 연산 횟수도 나와있다.

코드는 매우간단하다.

t=int(input())
 
 
fibo_list=[[0 for _ in range(2)] for _ in range(41)]
 
fibo_list[0]=[1,0]
fibo_list[1]=[0,1]
for i in range(2,41):
    fibo_list[i][0]=fibo_list[i-1][0]+fibo_list[i-2][0]
    fibo_list[i][1]=fibo_list[i-1][1]+fibo_list[i-2][1]
 
 
for i in range(t):
    n=int(input())
    print(fibo_list[n][0],fibo_list[n][1])