[#1003] 피보나치 함수

문제

#1003 피보나치 함수
Silver3
적용 알고리즘: 다이나믹 프로그래밍

---

풀이 방법

• 피보나치 점화식이 f(n) = f(n-1) + f(n-2) 이므로, 하위 호출되는 함수의 관계의 점화식도 이와 동일한 점을 이용한다.

코드 흐름

1. f(0)은 f(0)을 1번, f(1)을 0번 호출한다.
2. f(1)은 f(0)을 0번, f(1)을 1번 호출한다.
3. f(2)의 f(0), f(1)호출 횟수는 f(0)에서의 각각의 호출 횟수, f(1)에서의 각각의 호출 횟수의 합과 동일하다.
4. f(n)도 이와 동일하다

코드

fib01 = {0: [1, 0],
         1: [0, 1]}

for i in range(2, 41):
    fib01[i] = [fib01[i-1][0] + fib01[i-2][0], fib01[i-1][1] + fib01[i-2][1]]

t = int(input())
for i in range(t):
    n = int(input())
    print(fib01[n][0], fib01[n][1])

체감 난이도: 3/5
이전에 2193번을 풀고 이 문제를 풀으니 문제가 쉬웠다. 뭐든지 겁먹지 말고 문제를 푸는게 중요한 것 같다. 문제가 잘 풀리니 기분이 좋고 너무 재밌다… 난이도 높은 문제도 도전해봐야겠다.