📚 문제 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 📖 풀이 n이 1,000,000,000,000,000,000과 같이 주어졌으므로 점화식으로 더하면서 DP로 풀면 무조건 O(n) 이므로 무조건 시간초과가 발생한다. 피보나치 수를 해결할 수 있는 방법들을 찾아본다. 피사노 주기 피보나치는 정수로 나누면 주기가 나타난다. 피사노 주기는 1,000,000,007도 너무 커서 사용할 수 없다. 피사노 주기를 사용하기에는 모듈러 연산을 수행할 값이 너무 크다. 누승법, 행렬 멱법(Matrix Exponentiation) O..
