0927_Algorithm_1003_피보나치함수

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

초기 구상과정

• 피보나치 재귀함수 호출과정 그려보자
• 관계성 따지면 문제 해결될듯

최종 코드

import sys
input = sys.stdin.readline

for tc in range(int(input())):
    num = int(input())
    dp = [(1, 0)] + [0] * num
    if num >= 1:
        dp[1] = (0, 1)
    for i in range(2, num + 1):
        dp[i] = (dp[i-1][0] + dp[i-2][0], dp[i-1][1] + dp[i-2][1])

    print(dp[num][0], dp[num][1])

관계성 따지면서 그려보니 결국 재귀를 호출하는데 fibo(n-2) + fibo(n-1)을 호출하니 dp[n-2] + dp[n-1]이 되지 않겠나? 그래서 문제를 푸는데 간과할 뻔한 내용이 바로 1을 호출하는 경우. 이를 조건분기를 통해서 따로 해결하였다.

if num >= 1:
    dp[1] = (0, 1)

느낀점

간과하지말자, 극단적 경우와 시작과 끝