✓

태그:

14. 동적 계획법 1 CLASS 3 ESSENTIAL

N번째 피보나치 수를 재귀적으로 구할 때 0번째 피보나치 수와 1번째 피보나치 수를 몇 번 참조하는지 구하는 문제입니다. 이 문제는 memoization를 이용하여 각 정수마다 0과 1을 몇 번 참조하는지 저장하고 필요 시 꺼내쓰는 방식을 사용하여 풀 수 있습니다.

하지만 이를 조금 더 수학적으로 생각해보면 훨씬 쉽게 구할 수 있습니다. 먼저 N이 0일 때와 1일 때는 각각 [1, 0]과 [0, 1]로 정의되어있습니다. N이 2일 때에는 f(0)과 f(1)을 호출해야 하므로 [1, 1]이 됩니다. N이 3일 때에는 f(1)과 f(2)를 호출하는데, 각각 [0, 1]과 [1, 1]이므로 두 개의 합인 [1, 2]가 됩니다. 이제 여기서 0을 호출하는 횟수를 a_n, 1을 호출하는 횟수를 b_n라 놓고 점화식을 세워보겠습니다.

\[(a_n,b_n)=(a_{n-2}+a_{n-1},b_{n-2}+b_{n-1})(n\ge 2)\]

식을 가만보니 피보나치를 닮았네요. 그런데 실제로 보면, a₁과 b₀는 0, a₂과 b₁는 1로 피보나치의 정의와 같은 것임을 알 수 있습니다. 따라서 b_n은 F_n, a_n은 F_n-1과 같은 값을 가진다는 것을 유추할 수 있습니다. 따라서 n이 0인 경우를 제외하고는 피보나치 수열의 값을 가져다쓰면 된다는 것을 알 수 있습니다. 즉, \((a_n,b_n)=(F_{n-1},F_n)(n\ge 1)\)이 되는 것이죠.

소스 코드

언어	코드	시간
Python 3	코드(Github) / 코드(백준)	2020-03-31 13:49:34

---