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

https://www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

풀이

피보나치 수 1 = int

피보나치수 2 = long

피보나치수 3 = 피사노 주기

피보나치수 4 = BigInteger로 풀면된다.

 

(피보나치 수를 나눈 나머지는 항상 주기를 가진다. 이를 피사노 주기(Pisano Period)라 한다.)

1000000을 나눈 나머지를 한다는 가정하에 1500000번을 주기로 똑같은 값이 주어진다.

그러므로 size를 받아서 pisano로 나눈 나머지의 위치만 구해주면 되는 간단한 문제였다.

피사노 주기를 알고 있다는 가정하에..

 

소스코드

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		int pisano = 1500000;
		long size = Long.parseLong(br.readLine()) % pisano;
		
		long[] num = new long[pisano + 1];
		
		num[0] = 0;
		num[1] = 1;
		
		for(int i = 2; i <= pisano; i++) {
			num[i] = (num[i - 1] + num[i - 2]) % 1000000;
		}
		
		System.out.print(num[(int)size]);
	}
}