[BAEKJOON] 2749번 : 피보나치 수 3

문 제

 

소 스  코 드

#include <iostream>

typedef long long INT;

constexpr INT MOD{ 1'000'000 };
constexpr INT CYCLE{ MOD / 10 * 15 };

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	INT N;
	std::cin >> N;

	int *arr{ new int[CYCLE] };

	arr[0] = 0;
	arr[1] = 1;

	for (int i = 2; i < CYCLE; ++i) {
		arr[i] = (arr[i - 1] + arr[i - 2]) % MOD;
	}
	
	int answer{ arr[N % CYCLE] };

	std::cout << answer;

	delete[] arr;
}

 

풀 이

 

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

피보나치 수를 구하는 방법 중. 

처음에는, 피보나치 수열의 성질을 통하여 구현 하였지만, N이 1,000,000,000,000,000,000보다 작아야 한다는 규칙으로 인하여, 많은 루프를 동작하기 때문에 속도와 메모리의 문제가 생길 수 있었다. 새로운 방법을 찾는 중, 

나머지를 할 경우 나머지의 값이 반복 되는 "피사노 주기" 라는 방법을 알게 되었습니다.

 

N번째 피보나치 수를 M으로 나눈 나머지를 구할 경우, 

$$M = 10^{n} \quad (n > 2)$$

 

주기는, $$P = 15 * 10^{n - 1}$$

 

만약, 구하려는 N의 값이 P 이상일 경우에는 N % P를 하여 반복되는 값을 찾아서 결과를 도출해 낼 수 있다.

 

 

출 력 값

 

 

문 제  출 처

문제 링크 : https://www.acmicpc.net/problem/2749

2749번: 피보나치 수 3