[Python] 백준(BOJ) 1003번: 피보나치 함수 - dp

문제

1003번: 피보나치 함수

풀이

피보나치는 fib(i) = fib(i-1) + fib(i-2) 의 식을 세울 수 있기 때문에

i	0	1	2	3	4	5
fib(i)[0]	1	0	1	1	2	3
fib(i)[1]	0	1	1	2	3	5

위와같이 배열을 만들어서 0을 호출하는 횟수와 1을 호출하는 횟수를 저장했다.

문제 조건에서 i가 최대 40이라고 했기 때문에 미리 다 저장해두고 출력하는 방식으로 풀었다.

import sys

T = int(sys.stdin.readline())
arr = []

for i in range(41):
    if i == 0:
        arr.append([1, 0])
    elif i == 1:
        arr.append([0, 1])
    else:
        arr.append([arr[i-1][0] + arr[i-2][0], arr[i-1][1] + arr[i-2][1]])

for _ in range(T):
    num = int(sys.stdin.readline())
    print(arr[num][0], arr[num][1])