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

url : https://www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

 

수학적 지식이 필요한 문제!

피사노 주기

피보나치 수열을 어떤 숫자로 나눌 때 그 나머지들은 반복되는데, 이를 피사노 주기라고한다.

이 주기를 통해 큰 수에 대한 피보나치 수의 계산을 효율적으로 할 수 있다.

ex) 피보나치 수열을 3으로 나눌 때 나머지의 순서

(0, 1, 1, 2, 0, 2, 2, 1,) 0, 1 ..

=> 3에 대한 피사노 주기는 8

 

구하는 방법 (코드)

int pisanoPeriod(int m) {
    int prev = 0;
    int curr = 1;

    for (int i = 0; i < m * m; i++) {
        int temp = curr;
        curr = (prev + curr) % m;
        prev = temp;

        // 주기 찾으면 반환
        if (prev == 0 && curr == 1) {
            return i + 1;
        }
    }
    
    return 0;
}

 

✅ 10의 거듭제곱에 대해서는 주기가 예측 가능하다.

위 문제는 나누는 수가 10의 거듭제곱이므로, 피사노 주기를 직접 구하지 않고 알려진 값을 사용한다.

(직접 구하면 에러가 난다. 계산량이 너무 많기 때문이다.)

10^6의 피사노 주기 : 15 * 10^5 = 1500000

 

피사노 주기를 통한 반복성을 이용해 아주 큰 n의 피보나치에 대한 나머지를 구할 수 있다.

 

코드

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

int main() {
    const int MOD = 1000000;
    const int PISANO_PERIOD = 1500000;
    long long n;
    // 1. 입력받기
    cin >> n;
    //2. PISANO PERIOD 만큼 fib 채우기
    int fib[PISANO_PERIOD] = {0, 1};
    
    for (int i = 2; i < PISANO_PERIOD; ++i) {
        fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
    }
    //3. 정답 출력
    cout << fib[n % PISANO_PERIOD] << endl;

    return 0;
}

 

 

이러한 문제를 풀면서..과연 위 문제가 기업 코딩 테스트에 나올까 라는 생각이 들었다.

어떤 개념을 몰라서 (그것도 수학 관련 개념) 못 푸는 것이 알고리즘 대회가 아닌 이상 기업에서 바라는 일일까? 라는 생각이 들었다.

 

하지만 개인적으로는 피보나치 수를 구할때 n이 조금이라도 커지면 굉장히 큰 수가 되기때문에 걱정이 많았는데,

그 값을 나눈 나머지를 구한다면, 피사노 주기를 이용하면 된다는 사실을 알아서 안심도 되고 기뻤다!