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))