2749번

2749번 - 피보나치 수 3

이 문제는 피사노의 주기를 공부하면서 풀게되었다.

피사노의 주기는 피보나치의 수를 K로 나누었을 때 , 항상 주기가 생기고 이를 피사노의 주기라고 한다.

2749번은 N의 범위가 어마무시 하다.. 따라서 이를 DP를 이용한 캐시에도 한계가 있어서 , 우선 피보나치의 수를 모두 구할 수 없었다.

그래서 while 문을 통해서 주기를 찾고, 주기를 찾으면 바로 나와서 값을 구하는 방법으로 풀었다.

vector 에는 피보나치의 수를 mod 로 나눈 나머지를 계속해서 넣어줬고,

어떤 지점에서 vector 의 첫번째 원소와 같다면, 양 점( i , j ) 를 비교하면서 계속 증가시켜줬다. 그리고 그 때의 i-1 을 저장해둔다.

그래서 j가 i-1까지 가면 주기가 완성되므로 그 값을 이용해서 계산하면 된다.

추가적으로 깨닫게 된 사실

내가 풀었던 방법 처럼, 결국은 어떤 나누는 값 k에 대해서 피보나치의 수의 나머지들 만으로 수열을 구해도 상관이 없다.

왜냐하면 (A+B)%M = (A%M + B%M)%M 이기 때문에..

이말인 즉슨, 나는 주기를 구하기 위해 모든 값들을 비교했다. j 가 0 부터 flag 값이 될 때까지...

하지만 결국 우리는 피보나치의 0번째수=0, 1번째수=1 이라는 걸 알기에 , 다시 0 1 로 시작되면 주기가 생긴다는 점!!!! 

(꼭 0 1 이 아니라 두 개 값만 반복되면 주기라는 걸 알 수 있다. 메모리가 반이나 줄었다..)

무식하게 전부 다 확인하지 않아도 됐다. 밑에 코드 추가

번외) 

mod 값이 10^k 일때, k>2 이면 주기는 항상 15 * 10^(k-1) 이라는 쉬운 방법도 있다고 한다...

<정답 코드 - 전부 다 비교>

#include<iostream>
#include<vector>
using namespace std;
 
vector<long long> num;
const long long  mod = 1000000;
 
int main()
{
    long long  N;
    
    scanf("%lld", &N);
 
    num.push_back(0);
    num.push_back(1);
 
    long long i = 1;
    long long j = 0;
    long long flag = -1;
    bool cycle = false;
 
    while (!cycle)
    {
        i++;
        long long  temp = (num[i - 1]%mod + num[i - 2]%mod) % mod;
        num.push_back(temp);
        
        if (temp == num[j++])
        {
            if (flag == -1)
            {
                flag = i-1;
            }    
        }
        else
        {
            flag = -1;
            j = 0;
        }
 
        if (j == flag)
        {
            cycle = true;
        }
    }
 
    long long  size = j + 1;
    long long rest = N % size;
 
    printf("%lld\n", num[rest]);
 
    
 
    return 0;
}

<정답 코드 - 2개 값만 비교>

#include<iostream>
#include<vector>
using namespace std;
 
vector<long long> num;
const long long  mod = 1000000;
 
int main()
{
    long long  N;
    
    scanf("%lld", &N);
 
    num.push_back(0);
    num.push_back(1);
 
    long long i = 1;
    long long j = 0;
    long long flag = -1;
    bool cycle = false;
 
    while (!cycle)
    {
        i++;
        long long  temp = (num[i - 1]%mod + num[i - 2]%mod) % mod;
        num.push_back(temp);
        
        if (temp == num[j++])
        {
            if (flag == -1)
            {
                flag = i-1;
            }
            else
            {
                cycle=true;
            }
        }
        else
        {
            flag = -1;
            j = 0;
        }
    }
 
    long long  size = flag + 1;
    long long rest = N % size;
 
    printf("%lld\n", num[rest]);
 
    
 
    return 0;
}