백준 2749번 피보나치 수 3

< 백준 2749번 피보나치 수 3 - 마포 코딩박 >

사용한 알고리즘: 수학 (피사노 주기)


 피보나치 수를 K 로 나눈 나머지는 일정한 주기를 갖습니다. 이를 피사노 주기라고 합니다.
문제에서는 피보나치 수를 1000000로 나눈 나머지를 구하라 하였으므로 이 또한 피사노 주기를 갖습니다.
 저는 이 피사노 주기를 구해 문제를 해결하였습니다.

문제풀이는 다음과 같습니다.
(1) (코드: 20~34)
 MOD = 1000000 라 할 때 주기를 찾습니다.
 처음 시작이 0번째 피보나치수 = 0, 1번째 피보나치수 = 1 이므로 

 k번째%MOD = 0 , k+1번째%MOD = 1 이 되면, 주기가 발생합니다.
 왜냐하면 이후 k+2번째%MOD = k번째%MOD + k+1번째%MOD = 0+1 = 1 , 

 k+3번째%MOD = k+1번째%MOD + k+2번째%MOD = 1 +1 = 2, ... 일 수 밖에 없기 때문입니다.

(2) (코드: 36~50)
 입력받은 N번째 피보나치수 = (N%주기)번째 피보나치수 입니다.
 이를 찾아 출력해 줍니다.

 피사노 주기라는 개념을 알면 어렵지 않게 해결할 수 있는 문제였습니다.

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	const ll MOD = 1000000;
	ll n;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	// 피사노 주기 찾기
	ll one = 0;
	ll two = 1;
	ll period;
	ll temp;
	int idx = 2;
	bool Zero = false;
	// 주기 찾기
	// (k번째수)%MOD, (k+1번째수)%MOD 가 0, 1 이면 주기 발생
	// 이후 (k+2번째수)%MOD = (k번째수)%MOD + (k+1번째수)%MOD = 1 일 수 밖에없다.
	while(1){
	temp = two + one;
	temp%=MOD;
	// 앞 수가 0 이고, 지금 수가 1 이면 주기 발생
	if(temp==1LL && Zero){
	period = idx-1;
	break;
	}
	if(temp==0) Zero = true;
	else Zero = false;
	one = two;
	two = temp;
	idx++;
	}
	cin >> n;
	n%=period;
	if(n==0) cout << 0 << '\n';
	else if (n==1) cout << 1 << '\n';
	else{
	one = 0;
	two = 1;
	for (int i = 2; i <= n; ++i){
	temp = two+one;
	temp%=MOD;
	one=two;
	two=temp;
	}
	cout << temp << '\n';
	}
	return 0;
	}

view raw BOJ 2749.cpp hosted with ❤ by GitHub