[백준 - Python] 1003. 피보나치 함수 (DP)

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

1003번: 피보나치 함수

 

코드

T = int(input())

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

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


for _ in range(T):
    n = int(input())
    print(dp[n][0], dp[n][1])

 

피보나치 수열 문제는 DP에 대해서 처음 학습할 때 다뤘던 문제라

자신감을 갖고 문제를 풀기 시작할 수 있었다.

 

보통의 DP 문제와 달랐던 점은

1과 0이 출력 되는 횟수, 2가지 정보를 DP 리스트에 저장해야 했는데

문제에서 주어진 함수를 바탕으로

출력 결과를 적어보면서

i-1번째와 i-2번째 각각의

1이 출력 되는 횟수와 0이 출력 되는 횟수를

더해주면 i번째의  1과 0이 출력 되는 횟수임을 확인할 수 있었다.