[백준 파이썬] 1003 피보나치 함수

📌문제 출처

솔브닷 class 3+ 단계
https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

❓ 문제

 

❗ 풀이

• dp 활용

📗 풀이 코드

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    dp = {i:[] for i in range(n+1)}
    dp[0]=[1,0]
    dp[1]=[0,1]
    for i in range(2,n+1):
        dp[i] = [dp[i-1][j]+dp[i-2][j] for j in range(2)]
    print(*dp[n])

📗 코드 해설

• 피보나치 수열은 이전 두개의 수를 합친 결과이다.
• 따라서 이전 두개의 수를 불러올 때 0과 1이 몇번 호출되는지를 각각 합해주면 이번 수에서 0과 1 호출 횟수이다.
• dp에 각 인덱스번째 수열에서의 0과 1의 호출 횟수를 넣어줄 것이다.
• dp[0]과 dp[1]을 만들어 놓은 후 그 두 수의 0과 1의 호출 회수의 합을 통해 dp[2]부터 dp[n]까지 만들어준다.