목록빠른 거듭제곱 알고리즘 (1)

늘 겸손하게

백준 11444 ( C++)

피보나치 수 6 n 번째 피보나치 수를 구하면 되는 문제 이지만 n이 1,000,000,000,000,000,000 보다 작거나 같은 자연수이다. 재귀 함수를 이용하거나 단순하게 반복문으로 F2부터 Fn까지 구하려면 시간 초과가 발생한다. 시간 내에 문제를 해결하려면 다른 방식으로 접근해야 한다. 1. 방정식을 행렬식으로 표현 Fn+2 = Fn+1 + Fn 인 피보나치 수의 공식을 행렬 꼴로 바꾸어야 한다. 위 식만으로는 부족하므로 식 하나를 더 구한다. Fn+1을 Fn+1 = Fn+1 + 0 * Fn로 표현 가능하므로 위 두 식을 조합하면 위 식을 얻을 수 있다. 좌변의 를 u(n+1)로 보면 를 u(n)으로 표현할 수 있고 이고 A를 라고 하면 u(n+1) = A * u(n) 이 성립함을 알 수 있다..
코딩 문제/백준 2021. 7. 17. 15:29
이전 Prev 1 Next 다음