백준[2749] - 피보나치 수3

문제

백준 2749 문제 보기

접근 방법

피보나치 수열을 푸는 방식은 여러가지가 존재한다. 재귀를 활용하여 O(N^2)으로 푸는 방법, dp를 활용해 O(N)으로 푸는 방법이 많이 알려진 방식이다.
하지만 이번 문제는 입력이 10^18이라는 거대한 숫자이므로 저 두 가지 방법 모두 해답은 아니다.
여러가지 방법을 찾다가 피보나치 수열을 특정 수로 나눌때 주기가 존재한다는 pisano의 주기라는 방법을 알게되 이 방식을 적용해 풀었다.

코드

#include <iostream>

using namespace std;

long long N;
long long dp[1500010];

int main() {
    cin >> N;
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    if(N <= 2) {
        cout << dp[N];
        return 0;
    }
    for(int i = 3; i <= 1500000; i ++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000;
    }

    cout << dp[N % 1500000];
    return 0;
}