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

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

15624번: 피보나치 수 7

풀이

피보나치 수 문제인데 범위가 커져서 1,000,000,007로 나누는 문제이다.

나머지 분배법칙에 대해 자세히 알고있지 못하여 살짝 해맸는데 나머지 분배법칙만 잘 알고 있으면 dp를 사용하여 쉽게 풀수 있는 문제이다.

나머지 분배법칙의 증명은 다음 블로그를 참고하였다.

https://sexycoder.tistory.com/66

모듈러 연산의 성질과 증명

이 문제를 푸는것과는 관계가 없지만 공부를겸해서 나눗셈에 대한 나머지 분배 법칙 증명은 다음 블로그를 통해 알 수 있었다.

https://goodteacher.tistory.com/398

[알고리즘]나머지의 순환과 페르마 소정리

위에서 B^(p-2)는 잉여역수인데 이에대한 내용은 여기에 있다.

https://rikang.tistory.com/entry/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98-%EC%86%8C%EC%A0%95%EB%A6%AC-%EC%9E%89%EC%97%AC%EC%97%AD%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0

페르마의 소정리 ( 잉여역수 구하기 )

코드

#include<iostream>

using namespace std;

long long dp[1000000];
int main() {
    int n;

    cin >> n;

    dp[0] = 0;
    dp[1] = 1;
    dp[2] =1;
    for (int i = 3; i <= n; i++) {
        dp[i] =( (dp[i-1] % 1000000007) +(dp[i-2] % 1000000007)) % 1000000007;
    }
    cout << dp[n];




}