[분할 정복/ 파이썬] 백준 11444번 : 피보나치 수 6 / 골드 3

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

11444번: 피보나치 수 6

dp로 잘 알려진 피보나치 문제지만,
이 문제에선 n이 정말 큰 수로 주어지기 때문에 조금 다른 방법을 써야한다.
도가뉴 항등식이라고 있다.
n번째 피보나치 수를 a(n)이라 하면,

a(2n) = a(n)[a(n) + 2a(n-1)]
a(2n-1) = a(n)**2 + a(n-1)**2 가 성립한다.
따라서 n이 아무리 커도 log(n) 시간에 문제를 해결할 수 있기 때문에 이 문제를 풀 수가 있다.

import collections n = int(input()) m = 1000000007 dp = collections.defaultdict(int) dp[1] = 1 dp[2] = 1 def fib(n): if dp[n] != 0: return dp[n] if n%2 == 1: # odd b = n//2 a = b + 1 c = fib(a) d = fib(b) dp[n] = (c**2 + d**2)%m return dp[n] else: # even a = n//2 b = a - 1 c = fib(a) d = fib(b) dp[n] = (c**2 + 2*c*d)%m return dp[n] print(fib(n))