[C++] 백준 15624번: 피보나치 수 7

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

15624번: 피보나치 수 7

1. 문제풀이

 피보나치 수열은 다음과 같이 수식으로 표현하면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일 때까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
 주어진 문제에서 n의 범위는 0 ≤ n ≤ 1,000,000이다. n의 범위가 크므로, n번째 피보나치 수를 구하기 위하여 재귀함수가 아닌 다이나믹 프로그래밍으로 접근하였다. n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력하는 것이 또 하나의 관건이 된다. n번째 피보나치 수까지 구한 후, 1,000,000,007으로 나누는 생각을 할 수 있지만 정수를 표현하는 자료형의 범위를 넘어가기 때문에 오버플로우가 발생하여 n이 클 경우, 피보나치 수를 구할 수 없다.
 알고리즘해석및설계 시간에 공부한 모듈러 연산(Modular Arithmetic)의 성질 중, (A + B) % M = ((A % M) + (B % M)) % M을 이용하였다. n=17일 때 피보나치 수는 1597 이고 이를 10으로 나눈 나머지는 7이다. 모듈러 연산의 성질을 적용한 n=17일 때까지 피보나치 수를 10으로 나눈 나머지를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7
 마찬가지로 n=17일 때 피보나치 수를 10으로 나눈 나머지가 7인것을 확인할 수 있다.

2. C++ 코드

#include <iostream>
#include <stdio.h>

using namespace std;

int dp[1000001];

int main(void)
{
    int n;
    scanf("%d", &n);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
    }
    printf("%d\n", dp[n]);

    return 0;
}