[C++] BOJ 2749번: 피보나치 수 3

 

문제

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

 

입력 1

1000

출력 1

228875

코드

#include<iostream>
#include<cmath>

using namespace std;

//2749번 피보나치 수 3
//피사노 주기를 이용

long long arr[1500050];     //메모이제이션
int m = 1000000;            //나누는 수
int cycle;

int cycle_func() {
    int k=0,tmp=m;
    while (tmp > 1) {
        tmp /= 10;
        k++;
    }

    return 15 * pow(10, k - 1);
}

void pisano_fibo() {
    arr[0] = 0;
    arr[1] = 1;
    //파사노 주기에 의하여 1500000의 값들이 반복된 후에 다시 재 반복됨
    cycle = cycle_func();
    for (int i = 0; i < cycle; i++) {
        arr[i + 2] = (arr[i+1]+arr[i])%m;
    }
}

int main() {

    cin.tie(NULL);cout.tie(NULL);
    ios::sync_with_stdio(false);

    long long n;
    cin >> n;
    pisano_fibo();
    cout << arr[n % cycle];

    return 0;
}

 

*간단한 해설*

피사노 주기를 이용하여 푸는 문제이다 기본적으로 n의 범위가 1,000,000,000,000,000,000보다 작거나 같은 자연수 이기 때문에 기존에 쓰던 재귀함수를 이용하여서 푸는 방법은 시간이 매우 오래 걸리므로 쓸수가 없다. 따라서 피사노 주기를 통해 반복 주기를 찾고 그 주기동안의 피보나치 수열에서 m으로 나눈 나머지 값들을 배열에 저장한다. 그 후 저장한 배열에서 찾고자 하는 n번째가 주기에서 몇번째 숫자인지 찾아내서 해당 배열의 값을 출력하면 된다. 피사노 주기는

나누는 값을 M이라고 지칭했을 때,

M=10^k , cycle = 15 x 10^(k-1)

이다.

 

 

 

 

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*