[ BOJ 1003 ] 피보나치 함수(Python)

문제

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

재귀 형태의 피보나치 함수가 있을 때, fibo(n)에 대해서 fibo(0)과 fibo(1)이 몇번 호출되는지 구하는 문제다.

---

문제 풀이

문제를 처음 접했을 때 어떻게 접근해야 할지 감이 안잡혔다.
그래서 직접 써내려가면서 f(0),f(1)의 호출 횟수를 표로 정리를 해보았다.

f(n) = (0 호출 횟수, 1 호출 횟수)

f(0) = (1, 0)
f(1) = (0, 1)

f(2) = f(0) + f(1) 
     = (1, 1)
     
f(3) = f(1) + f(2)
     = f(1) + f(0) + f(1)
     = (1, 2)

f(4) = f(2) + f(3)
     = (1, 1) + (1, 2)
     = (2, 3)
     
f(5) = f(3) + f(4)
     = (1, 2) + (2, 3)
     = (3, 5)

n	0	1	2	3	4	5	6
f(0) 호출 횟수	1	0	1	1	2	3	5
f(2) 호출 횟수	0	1	1	2	3	5	8

✨ 0과 1의 호출 횟수 또한 피보나치 수열을 따르는 것을 확인할 수 있다.

• f(n)의 f(0) 호출 = f(n-1)의 f(0) 호출 + f(n-2)의 f(0) 호출
• f(n)의 f(1) 호출 = f(n-1)의 f(1) 호출 + f(n-2)의 f(1) 호출

따라서 n이 0이거나 1일 때 예외 상황을 만들어주고,
그 외에는 보통의 피보나치 수열과 동일하게 풀이했다.

---

코드

import sys

dp = [0] * 41

def fibo(n):
    print(dp)
    if dp[n] != 0:
        return dp[n]
    if n<2:
        return n
    else:
        dp[n] = fibo(n-1)+fibo(n-2)
        return dp[n]
    

T=int(sys.stdin.readline())

for i in range(T):
    case = int(sys.stdin.readline())
    
    if case == 0:
        print(1,0)
    elif case == 1:
        print(0,1)
    else:
        print(fibo(case-1),fibo(case))