백준 BOJ 15624 - 피보나치 수 7

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

15624번: 피보나치 수 7

기초적인 1차원 DP에 대해 묻고있는 문제.

 

$F_n = F_{n-1} + F_{n-2}$

공식에 맞게 dp 테이블을 구현해주면 된다.

1e9+7로 나눈 나머지를 출력해줘야 하는데,

전부 저장해뒀다가 출력시에만 1e9+7로 나누려고 하는 경우

피보나치값들이 매우 커져서 오버플로우가 발생할 수 있다.

 

정수론 모듈러 연산의 특징에 의해

$(A \pm B) mod C = (A mod C \pm B mod C) mod C$

이고,

$A$, $B$ 가 각각 dp테이블의 값,

$C$가 1e9+7(1,000,000,007) 에 해당하게끔 식을 구성,

즉 매번 DP를 계산해줄때마다

dp[i] % 1e9+7 으로 나머지를 저장해줘야 한다.

 

파이썬의 경우에는 수 범위제한이 없으므로 아마 그대로 저장해도 되지 싶다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll fibo[1234567] = {0};

int main(){
	fibo[0] = 0;
	fibo[1] = 1;
	for(int i=2; i<1234567; i++){
		fibo[i] = fibo[i-1] + fibo[i-2];
		fibo[i] %= 1000000007;
	}
	
	int N;
	cin >> N;
	cout << fibo[N];
	return 0;
}