[11444번] 피보나치 수 6

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. Map STL

3. 피보나치 점화식

큰 수에 대해서 피보나치를 어떻게 구하는지 찾다보니 다음과 같은 피보나치 점화식이 존재함을 알 수 있었다.

이 방식을 토대로 DP를 짠다.

이때 DP를 짜는 것은 모든 값을 다 이용하는 것이 아닌, 그 값에 해당하는 필요한 값에 대해서만 DP에 넣어준다.

이 문제를 푼다면 다음 문제도 참고하길 바란다.

이 문제와는 다른 문제이지만, 접근 방식이 MAP DP로 접근이 가능하다.

[1351번] 무한 수열 :: http://www.crocus.co.kr/635

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

#include <iostream> #include <map>   #define mod 1000000007   using namespace std;   typedef long long ll;   map<ll, ll> m;   ll fibo(ll n)  {     if (n == 1)          return 1;          else if (n == 2)          return 1;          else if (m[n])         return m[n];          else      {         if (n % 2 == 1)          {             ll t = (n + 1) / 2;             ll Fn = fibo(t);             ll Fn1 = fibo(t - 1);               m[n] = (Fn * Fn + Fn1 * Fn1) % mod;               return m[n];         }           else          {             ll t = n / 2;             ll Fn1 = fibo(t - 1);             ll Fn = fibo(t);               m[n] = (2 * Fn1 + Fn) * Fn % mod;               return m[n];         }     } } int main()  {     long long n;          scanf("%lld", &n);       printf("%lld", fibo(n));       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus