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

 

---

 

• 문제 풀기 전 알아야 할 것

정답 코드 : 피보나치 문제풀 때 재귀로 풀었던 것이 생각이 나서 재귀로 풀려니까 시간이 너무 많이 걸릴 것 같아서 배열로 하자니 수가 너무 커서 주기가 있을 것 같아서, 피보나치 주기를 쳐보니 해결책이 나왔다.

 

피보나치 수를 K로 나눈 나머지는 항상 주기를 가지게 됩니다. 이를 피사노 주기(Pisano Period)

 

주기의 길이가 P 이면, N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M을 나눈 나머지와 같습니다. M = 10^k 일 때, k > 2 라면, 주기는 항상 15 × 10^(k-1) 입니다. 이 사실을 모른다고 해도, 주기를 구하는 코드를 이용해서 문제를 풀 수 있습니다. 이 문제에서 M = 10^6 이기 때문에, 주기는 15 × 10^5 = 1500000가 됩니다.

 

• 코드

정답 코드 : 위의 내용을 토대로 코드를 작성하였다. 주기를 찾아서 "입력한 수의 % 1500000 크기"의 배열을 만들어서 피보나치 수열을 정렬하였고, "입력한 수의 % 1500000 크기"번째의 값을 출력했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
		long number = Long.parseLong(br.readLine());
		int cycle = (int)(number % 1500000);
		
		long[] fibonacciArray = new long[cycle+1];
		
		fibonacciArray[0]=0;
		fibonacciArray[1]=1;		
		
		for (int i = 2; i <= cycle; i++) 
			fibonacciArray[i] = (fibonacciArray[i-1] + fibonacciArray[i-2])%(long)Math.pow(10,6);
		
		System.out.println(fibonacciArray[cycle]);		
    }
}

 

다른 사람의 코드 : 나보다 속도가 빠르다. 사용한 방법은 행렬을 이용한 방법이다. 공부해두면 좋을 것 같다.

 

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static BigInteger N;
    static long[][] matrix = new long[2][2];
    static int mod = 1000000;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = new BigInteger(br.readLine());
        if (N.equals(new BigInteger("1"))) {
            System.out.println(1);
        } else {
            matrix[0][0] = 1;
            matrix[1][0] = 1;
            matrix[0][1] = 1;
            matrix[1][1] = 0; // 피보나치 수를 구하는 하나의 방식, 나머지는 DP와 일반항
            matrix = getFibo(N.subtract(new BigInteger("1")));
            System.out.println(matrix[0][0]);
        }
    }

    private static long[][] getFibo(BigInteger N) {
        if (N.equals(new BigInteger("1")))
            return matrix;
        long[][] P = getFibo(N.divide(new BigInteger("2")));
        if (N.mod(new BigInteger("2")).equals(new BigInteger("0"))) {
            return MultiMatrix(P, P);
        } else {
            return MultiMatrix(MultiMatrix(P, P), matrix); // 아마 오버플로우는 없을 것이다
        }

    }

    private static long[][] MultiMatrix(long[][] A, long[][] B) {
        long[][] M = new long[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    M[i][j] += A[i][k] * B[k][j];
                    M[i][j] %= mod; // 추측: mod 연산은 이것만으로 충분할 것
                }
            }
        }
        return M;
    }

    // private static void Print(long[][] arr) {
    //     System.out.println();
    //     for (int i = 0; i < 2; i++) {
    //         for (int j = 0; j < 2; j++) {
    //             System.out.print(arr[i][j] + " ");
    //         }
    //         System.out.println();
    //     }
    // }
}