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

 

 

<코드>

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

long long N, cnt;
vector<int> v;

void pisano(int m)
{
	v.push_back(0);
	v.push_back(1);
	v.push_back(1);
	cnt = 2;

	while (1)
	{
		v.push_back((v[cnt] + v[cnt - 1]) % m);
		cnt++;

		if(v[cnt] == 0 && v[cnt-1] == 1) break;
	}
}

int main()
{
	cin >> N;

	pisano(1000000);

	cout << v[N % cnt];

}

 

 

풀이 방법

cocoon1787.tistory.com/307

[C/C++] 백준 9471번 - 피사노 주기

이번 문제 2749번 피보나치 수 3 를 풀기 전에 위의 문제를 풀어보는 것을 추천드립니다.

문제 풀이의 결론부터 말씀드리자면 나머지가 1,000,000일 때 주기는 1,500,000이 됩니다.
확인 차 피사노 주기 코드로 나머지를 1,000,000로 입력해보니 주기는 1,500,000로 계산되었습니다.

 

그러나 이번 문제 코드는 주기를 모르는 상태에서 수열과 주기를 둘 다 구할 수 있는 함수를 만들어서 풀이를 하였습니다. pisano함수의 파라미터 m은 나머지를 뜻하며 초기의 피보나치 수열 0,1,1을 벡터 v에 push 하고 주기를 구할 때까지 무한루프를 돌게 됩니다. 그리고 주기(cnt)를 구하면 루프 문을 탈출하고 입력으로 주어진 N에서 v벡터의 [N% cnt] 번째 원소를 출력하면 정답을 맞힐 수 있습니다.

 

 

www.acmicpc.net/problem/2749

2749번: 피보나치 수 3