백준 02749 - 피보나치 수 3

출처 : https://www.acmicpc.net/problem/2749 

2749번: 피보나치 수 3

 

고려사항

• 피보나치를 푸는 대표적인 dp를 활용한 방법 외에도 여러가지를 알게 되었다.
  1) 행렬이용 ( 11444번 )
  2) 피사노 주기 ( 위 문제 )
  3) 일반항 이용 ( 아직 안 풀어봄... )
• n번째 피보나치 수를 구하는 문제는 일반적으로 n이 48만 넘어가도, INT_MAX를 넘어가는 큰 수이기 때문에
  특정한 수 x로 나눈 나머지를 구하라라는 문제로 연결된다.
• 이 때, x의 나머지 연산은 피보나치 수열이 특정 주기별로 반복되어 나타나도록 하는데, 이를 피사노 주기라 한다.
  피사노 주기는 위 문제처럼, x가 10^k 꼴이라면 => 15 * 10^(k-1) 간단히 계산할 수 있는데, 이 외의 수에도 할 수 있는걸로 확인되지만
  아직 풀어보지는 않았다..! ( 9471 문제 참고 )
• % 1500000 을 활용하여 재귀로 구현을 했었는데, tail call recursive로 구현을 하지 않았기도 했고,
  극단적으로 n = 5000 일때도, stack overflow가 뜨는 거 같아서, 반복문으로 구현 했다.
  (일반적으로 stack에 함수가 쌓일 수 있는 크기가 4792 번 정도 인 것 같다!)
• 같은 문제를, 행렬과 피사노 주기를 이용해서 풀어보았다.
  사진상으로도 알 수 있듯이, 행렬곱을 활용하는 것이 훨씬 효율적이다...
  피사노 주기는 x 값에 의존적이니 행렬을 적극 활용하도록 하자..!

(상) - 피사노 주기       (하) - 행렬 이용

 

#include <iostream>
#include <string.h>
using namespace std;

int fib[1500000] = {0, 1};

int main() {
    long long n;

    cin>>n;
    n %= 1500000;
    for(int i=2;i<=n;++i){
        fib[i] = (fib[i-1] + fib[i-2]) % 1000000;
    }

    cout<<fib[n];
    return 0;
}