BOJ 1003번: 피보나치 함수

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

문제풀이:

dp[0] = [1,0]

dp[1] = [0,1]

dp[i][0] = dp[i-1][0] + dp[i-2][0]

dp[i][1] = dp[i-1][1] + dp[i-2][1]

 

이미 구해놓은 수열은 반복하여 구하지 않고 바로 출력할 수 있도록 idx를 매번 업데이트 해주었다.

import sys

T = int(sys.stdin.readline())
dp = [[0,0] for _ in range(41)]
dp[0] = [1,0]
dp[1] = [0,1]
idx = 2
for _ in range(T):
    N = int(sys.stdin.readline())
    for i in range(idx,N+1):
        dp[i][0] = dp[i-1][0]+dp[i-2][0]
        dp[i][1] = dp[i-1][1]+dp[i-2][1]
    idx = max(idx,N+1)
    print(dp[N][0], dp[N][1])