2749번

요즘 들어 백준 문제를 풀고 있는 중이다. DP 문제에 익숙해지기 위해서 새로운 유형의 문제부터 많이 익숙한 문제들을 풀던 도중, 피보나치 수인데 정답률이 상대적으로 낮은 문제를 보고 의아함이 생겨  풀어보게 되었다. 

 

문제 조건 중 가장 눈여겨 보야할 점은 

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

이 부분

 

내가 작성한 코드는 다음과 같았다. 

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        long num = sc.nextLong();
        long fibo[] = new long[(int) (num+1)];

        fibo[0] = 0;
        fibo[1] = 1;
        for(int i = 2; i<=num; i++){
            fibo[i] = (fibo[i-1] + fibo[i-2])%1000000;
        }
        System.out.println((fibo[(int) num])%1000000);
    }
}

개인정보 가리기

결과도 문제의 입출력 예시에 맞게 나왔다. 

하지만 제출 결과는 

아무리 코드를 성형해보아도 해결되지 않았고 

어떤 특정한 규칙이 있는지 싶어 검색을 해보았다. 그 결과 알게 된 것이 파사노 주기

파사노주기에 대해 복습해보도록 하겠다

 

 

피사노주기

 

피보나치 수를 K로 나누었을 때 가지게 되는 주기를 피사노 주기라고 한다. 

 

N%M == (N%P)%M

M = 10^K 일 때 K>2라면 주기는 항상 15*K-1이라는 공식이 성립한다*P는 피사노주기*

 

 

다시 푼 코드 

 

import java.util.Scanner;

 
public class Main {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        long num = sc.nextLong();
       
        // long fibo[] = new long[(int) (num+1)];

        int pisano_period = 1500000;
        long size = num%pisano_period;
        long fibo[] = new long[pisano_period+1];

        fibo[0] = 0;
        fibo[1] = 1;
        for(int i = 2; i<=pisano_period; i++){
            fibo[i] = (fibo[i-1] + fibo[i-2])%1000000;
        }
        System.out.println((fibo[(int) size])%1000000);
    }
}
//N%1000000 == (N%(15*10^5))%1000000

주목할 점은

1.pisano 주기를 구해준 것. 

2.num%pisano_period > 이를 통해 결국 cycle 별 피사노 주기에 맞는 나머지를 바로 입력할 수 있도록 간단하게 해줄 수 있었음. 무슨 말이냐면 1이든 15000001이든 결국 주기에 의해 배열의 같은 칸에, 같은 나머지를 가지게 된다는 것을 이용하는 것임 

 

이렇게 pisano 주기를 이용하니 해결할 수 있었음

피보나치수열은 쉽다고 생각했었는데, 공부를 계속하니 하면 할수록 정말 할게 많은 것 같다. 

고민을 하느라 시간을 좀 썼지만, 새로운 지식을 하나 얻어갔으니 그걸로 만족이다. 

피사노 주기 ! 잊지말자