[백준 2749] 피보나치 수3(Java)

1. 문제

www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

2. 풀이

• 피사노 주기라는 것에 대해 알게 되었다.
• 피보나치는 재귀, DP, 피사노주기 3가지 방법으로 풀이가 가능하다고 한다.

3. 코드

import java.util.Scanner;

public class Main {

    
    //피사노 주기
    static final int mod =1000000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long num = sc.nextLong();
        //15 * 10의 n제곱

        int pisano = 1500000;

        num = num%pisano;

        long[] fibo = new long[pisano+1];
        fibo[1] = 1;

        for(int i=2; i <= pisano; i++) {
            fibo[i] = (fibo[i-1] + fibo[i-2])%mod;
        }

        System.out.println(fibo[(int)num]);
    }

}

반응형