[백준] 2749 : 피보나치의 수 3 (JAVA) / 피보나치 수 구하는 방법, 재귀, 메모이제이션, 행렬)

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 전형적인 피보나치 문제인데, 골2길래 뭔가 싶어 풀어봤다. 이 문제의 주의할 점을 몇가지 뽑자면 입력값 n의 크기가 10^18 로 매우 크다. int 형이 아닌 long 으로 입력을 받아야한다. n번째 피보나치 수를 구하기에, n이 매우 크므로 재귀방식이 아닌 행렬을 사용해풀어야 하지만 이 또한 n이 크기 때문에 O(n) 으로는 해결하기 애매하다. 1,000,000 으로 나눈 나머지를 출력한다는 부분이 힌트. 결론적으로 피사노 주기(Pisano Period)를 이용하여 풀어야하..

원문링크 : [백준] 2749 : 피보나치의 수 3 (JAVA) / 피보나치 수 구하는 방법, 재귀, 메모이제이션, 행렬)