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

문제

[C++] 백준 2749: 피보나치 수 3 GOLD 2
https://www.acmicpc.net/problem/2749

 

---

 

접근 방법

백준 2749번은 N번째 피보나치 수를 1,000,000으로 나눈 나머지를 구하는 문제다.

 

문제의 핵심은 N의 범위가 매우 크다는 것이다.
N은 최대 10^18까지 주어질 수 있기 때문에, 단순히 피보나치 수열을 N까지 계산하는 방법으로는 해결할 수 없다.

 

이 문제를 해결하기 위해 피사노 주기(Pisano Period) 개념을 이용한다.

피보나치 수열을 어떤 수 m으로 나눈 나머지는 반복되는 주기를 가진다.
이 반복되는 길이를 피사노 주기라고 한다.

 

이 문제를 풀기 전에 백준 9471번 문제를 먼저 풀고 오는 것을 추천한다.

관련 포스팅:

https://xeungcoding.tistory.com/111

[C++] 백준 9471: 피사노 주기

 

예를 들어, 피보나치 수열을 1,000,000으로 나눈 나머지는 1,500,000의 주기를 가진다.

즉, 아래의 성질을 이용하면 N이 매우 커도 주기 범위 안으로 줄여서 계산할 수 있다.

F(n) % 1,000,000 = F(n % 1,500,000) % 1,000,000

 

따라서 풀이 과정은 다음과 같다.

1. 피사노 주기 계산
2. n % 주기 로 실제 계산해야 할 피보나치 인덱스 구하기
3. 해당 인덱스까지 피보나치 수열 계산

 

상세 아이디

1.  피사노 주기 구하기

피사노 주기는 다음 성질을 가진다.

k(m) ≤ m² - 1

따라서 다음처럼 반복하면서 다시 (1, 1)이 등장하는 순간을 찾으면 된다.

int pisano(LL n)
{
    LL previous = 1, current = 1;
    LL k = 0;

    for (LL i = 0; i < n * n; i++)
    {
        k = (previous + current) % n;
        previous = current;
        current = k;

        if (previous == 1 && current == 1)
            return i + 1;
    }
}

 

m = 1,000,000일 때 피사노 주기가 1,500,000 이기 때문에, 

pisano 함수를 사용하지 않고 아래와 같이 값을 직접 사용해도 된다.

LL k = 1500000;

 

2. 실제 계산할 인덱스 구하기

주기를 이용하면 계산해야 할 인덱스는 아래와 같다.

LL index = n % k;

즉, N번째 피보나치 수를 직접 구할 필요 없이 index번째 피보나치 수만 계산하면 된다.

 

3. 피보나치 계산

vector<LL> fibo(index + 2, 0);
fibo[1] = 1;

for (LL i = 2; i <= index; i++)
    fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1000000;

피보나치 값 자체는 매우 커지므로 항상 % 1000000을 해주면서 계산해야 한다.

 

구현 시 주의할 점

• N이 최대 10^18이기 때문에 반드시 long long을 사용해야 한다.
• 피보나치 값을 그대로 계산하면 안 된다
  • 피보나치 수는 매우 빠르게 커지므로 매 단계마다 mod 연산을 해줘야 한다.
• 피사노 주기를 이용해야 시간 내 해결 가능

 

---

 

코드

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

typedef long long LL;

int pisano(LL n)
{
	LL previous = 1, current = 1;
	LL k = 0;
	for (LL i = 0; i < n * n; i++)  // k(m) <= m^2 - 1
	{
		k = (previous + current) % n;
		previous = current;
		current = k;

		if (previous == 1 && current == 1)
			return i + 1;
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	LL n = 0;
	cin >> n;

	LL k = pisano(1000000);  // 반복되는 주기 = 1,500,000
	LL index = n % k;

	vector<LL> fibo(index + 2, 0);
	fibo[1] = 1;
	for (LL i = 2; i <= index; i++)
		fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1000000;

	cout << fibo[index];
}