파이썬 백준 1003번 : 피보나치 함수

문제

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

1003번: 피보나치 함수

 

 

풀이

다이나믹 프로그래밍을 이용해서 해결했다.

N일때 0의 호출은 N-1의 1의 호출과 동일하다. 

import sys

d=[0]*41 # 계산된 결과를 저장하기 위한 DP 테이블
d[1]=1 # 첫 번째 피보니치 수
d[2]=1 # 두 번째 피보나치 수
T = int(sys.stdin.readline())

for _ in range(T):
    N = int(sys.stdin.readline())
    for i in range(3,N+1): # 3번째 부터 N번째 까지 피보니치 수 계산 
        d[i]=d[i-1]+d[i-2]
    # 0이 호출된 수와 1이 호출된 수 출력    
    if N==0:
        print('1',end=' ')
    else:
        print(d[N-1],end=' ')
    print(d[N])