BOJ 2749 피보나치 수 3

www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

이번엔 피보나치 수 3을 풀어봤다. 

입력받는 N이 무려 \(10^{18}\) 이다...

내가 알기에 Long Long int 형이 딱 저 자릿수에 걸치는 걸로 안다.

이 문제는 피사노 주기를 이용해서 풀어야 한다.

피보나치 수열은 어떤 값으로 나눌 경우 특정한 주기를 갖는데 이 문제에서는 나누는 값이 백만으로 매우 작아서 피사노 주기를 이용하여 풀 수 있다.

 

	do {
		int tmp = m1;
		m1 = m2;
		m2 = (tmp + m1) % MOD; len++;
	} while (m1 != 0 || m2 != 1 || !len);

나누는 값에 대해서 주기 Len을 구해준다.

 

	int* d = new int[len];
	d[0] = 0, d[1] = 1;
	for (int i = 2; i <= len; i++) {
		d[i] = d[i - 1] + d[i - 2];
		d[i] %= MOD;
	}
	cout << d[n % len] << endl;

그 주기의 크기만큼 배열을 할당해주고 각각 피보나치 수열을 구해주면 된다.

d 배열은 전역 변수로 선언해주려 했는데 마땅한 방법이 없어서 동적 할당해줬다.

 

#include <iostream>
using namespace std;

const int MOD = 1e6;

int main() {
	int m1 = 0, m2 = 1, len = 0;
	long long n;
	cin >> n;

	do {
		int tmp = m1;
		m1 = m2;
		m2 = (tmp + m1) % MOD; len++;
	} while (m1 != 0 || m2 != 1 || !len);

	int* d = new int[len];
	d[0] = 0, d[1] = 1;
	for (int i = 2; i <= len; i++) {
		d[i] = d[i - 1] + d[i - 2];
		d[i] %= MOD;
	}
	cout << d[n % len] << endl;

	return 0;
}