피보나치 수열 : 피사노 주기 직접 찾아서 문제 풀기 (백준 BOJ 2749)

특이한 방식으로 해결하는 문제가 있어 풀이하기 위해 가져왔습니다.

백준 BOJ 2749번 문제인 '피보나치 수 3' 문제로, 풀이 코드를 작성하기 전 미리 별도의 코드를 작성하여 풀이에 대한 정보를 찾아야 하는 문제입니다.

 

 

백준 BOJ 2749 : 피보나치 수 3

피보나치 수의 0번째 항을 0, 1번째 항을 1로 두며, f[i] = (f[i-1] + f[i-2]) % 1000000라고 정의할 때 10^18 이하 번째의 피보나치 수의 값을 찾는 문제입니다.

 

피보나치 수를 K로 나눈 나머지는 항상 주기를 가진다는 성질이 있고, 이 때의 주기를 '피사노 주기'라고 합니다.

다만 우리는 이 성질을 모르더라도 아래와 같이 주기를 찾기 위해 시도를 해볼 수는 있습니다.

 

 

#include <bits/stdc++.h>
#define MOD 1000000
using namespace std;

int fibo[3000000] = {0, 1};

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

    for(int i=2; i<3000000; i++)
        fibo[i] = (fibo[i-1] + fibo[i-2]) % MOD;

    for(int i=2; i<2999000; i++) {
        bool check = true;
        for(int j=1; j<=10; j++)
            if(fibo[j] != fibo[i+j]) check = false;

        if(check) cout << i;
    }
}

 

300만으로 잡은 것은 그냥 대략적으로 잡은 것입니다.

시도를 해서 주기가 나오지 않는다면 다른 방법을 찾으면 되는 것이고, 주기가 얻어진다면 그대로 풀이할 수 있는 것입니다.

 

 

 

실행 결과 위와 같이 주기가 150만임을 알 수 있습니다.

따라서 우리는 150만까지는 나머지 값을 저장하고, 그보다 큰 번째 수에 대해서는 150만으로 나눈 번째 배열의 값을 출력해주면 됩니다.

 

 

#include <bits/stdc++.h>
#define MOD 1000000
using namespace std;

int fibo[1500001] = {0, 1};

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

    for(int i=2; i<=1500000; i++)
        fibo[i] = (fibo[i-1] + fibo[i-2]) % MOD;

    long long N; cin >> N;
    cout << fibo[N % 1500000];
}

 

따라서 위와 같이 주기 150만에 대한 규칙성을 이용하여 피보나치 수를 찾아주면 됩니다.

150만번째까지는 어쩔 수 없이 dp를 활용하여 배열에 값을 저장해주도록 합니다.

 

---

+ 추가 풀이

백준 BOJ 11444 : 피보나치 수 6 문제의 풀이인 "행렬 + 분할정복을 이용한 거듭제곱"을 활용하면 피사노 주기가 매우 큰 경우에 대해서도 더욱 일반적으로 피보나치 수를 구할 수 있습니다.

 

 

#include <bits/stdc++.h>
#define MOD 1000000
using namespace std;

typedef vector<vector<long long>> matrix;

matrix multiply(matrix& A, matrix& B) {
    matrix C = {{0, 0}, {0, 0}};

    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % MOD;

    return C;
}

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

    long long N; cin  >> N;
    matrix ans = {{1, 0}, {0, 1}}, A = {{1, 1}, {1, 0}};

    while(N > 0) {
        if(N % 2 == 1)
            ans = multiply(ans, A);
        A = multiply(A, A);
        N /= 2;
    }

    cout << ans[0][1];
}

 

위의 코드에 대한 설명은 저의 다른 포스트에 정리되어 있으니 참고해주시면 될 것 같습니다.

 

↓ 해당 포스트에 대한 링크는 아래에 첨부되어 있습니다.

[백준/BOJ] 11444번 : 피보나치 수 6 (분할정복 거듭제곱, 행렬 식 조작)