[백준] 1003번 피보나치 함수 (Python 파이썬)

DP(dynamic programming)을 이용해서 풀 수 있는 문제였다. 

 

예를 들어 피보나치 함수는 f(i) = f(i-1) + f(i-2) 라는 점화식이 적용되는데, 이는 피보나치 수의 값 뿐만 아니라 문제에서 나오는 0과 1의 출력 횟수에도 동일하게 적용된다. 

 

import sys
input = sys.stdin.readline

dp = [[0, 0] for _ in range(41)]
dp[0][0], dp[0][1] = 1, 0
dp[1][0], dp[1][1] = 0, 1

for i in range(2, 41):
    dp[i][0] = dp[i-1][0] + dp[i-2][0]
    dp[i][1] = dp[i-1][1] + dp[i-2][1]
    
T = int(input())
for _ in range(T):
    N = int(input())
    print(str(dp[N][0]) + " " + str(dp[N][1]))