Little Jay

[C++] 백준 2749번 피보나치 수 3 본문

알고리즘/BOJ

[C++] 백준 2749번 피보나치 수 3

Jay, Lee 2021. 7. 23. 15:55

앞의 글을 참조해야 한다

피사노 주기를 통해서 어떤 피보나치 수를 1000000으로 나눈 주기는 1500000이다.

따라서 n에 어떤 수가 들어오더라도

n mod 1500000의 값만 찾으면 된다.

또한 미리 피보나치 배열을 하나 만들어 놓으면 메모리 누수가 적을 것이다.

 

#include <iostream>
#include <vector>
using namespace std;

long long a[1500010];

void fibo() {
	a[0] = 0;
	a[1] = 1;
	for (int i = 0; i < 1500000; i++) {
		a[i + 2] = (a[i + 1] + a[i]) % 1000000;
	}
}

int main() {

	long long n;
	cin >> n;
	fibo();
	cout << a[n % 1500000] << "\n";

	return 0;
}

'알고리즘 > BOJ' 카테고리의 다른 글

[C++] 백준 17608번 막대기  (0) 2021.07.30
[C++] 백준 1436번 영화감독 숌  (0) 2021.07.23
[C++] 백준 9471번 피사노 주기  (0) 2021.07.23
[C++] 백준 1920 수 찾기  (0) 2021.07.18
[C++] 백준 15829번 Hashing  (0) 2021.07.18
Comments