[baekjoon 2749] 피보나치 수 3 (DP, 피사노 주기) (C++)

www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

평범한 피보나치 수를 구하는 문제인 것 같지만 주어지는 수의 범위가 10^18이다.

따라서 저만큼의 크기를 갖는 DP 배열을 생성하는 것은 불가능하기에 다른 방법을 이용해야 한다.

 

피보나치 수를 일정한 크기의 수로 나눈 나머지는 파사노 주기라고 하는 주기를 갖는다고 한다.

주기를 갖게 되면 N을 구하더라도 N%P(주기)와 같은 값을 갖게 된다.

www.acmicpc.net/blog/view/28

피보나치 수를 구하는 여러가지 방법

백준 블로그에 백준 님이 올리신 글이다.

 

M이 10^K이고 K>2 이상의 수로 나눌 때 주기를 구하는 공식은 15*10^(K-1)이다.

따라서 엄청 큰 수가 들어와도 이 문제는 1,000,000으로 나눈 나머지를 구하는 문제이므로

총 0~15*10^5-1의 범위의 피보나치 수 내에서 정답이 구해질 것이다.

 

#include <iostream>
#include <cmath>

#define MOD 1000000 //10^6

using namespace std;

int P;
long long dp[1500000], n;

int main() {
	cin >> n;
	P = 15 * pow(10, 5); // 주기 구하는 공식 : 15 * 10^(n-1)
	int input = n % P;
	dp[1] = 1;
	dp[2] = 1;

	for (int i = 2; i <= input; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
	}

	cout << dp[input];
}

또한 피보나치를 구할 때 재귀 함수로 구하면 오류가 난다.

주어진 N을 주기로 나눈 나머지지만 몇십만의 값이 나오게 되면 함수 호출 스택의 크기를 넘어서게 된다.

따라서 FOR문을 통해서 구해주었다.