2023/04/071 [Kotlin] 백준 11440 : 피보나치 수의 제곱의 합 문제 링크 11440번: 피보나치 수의 제곱의 합 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해설 입력의 최대치가 \(10^{18}\)이기 때문에 피보나치 수를 각각 구해서 제곱하여 더하는 방법으로 풀게 되면 어마어마한 시간이 걸리므로 다른 방법을 사용하여 풀어야 한다. 피보나치 수의 기본적인 점화식인 \(F_n=F_{n-1}+F_{n-2}\)를 살짝 변형하면 \(F_n=F_{n+1}-F_{n-1}\)이 되는데, 이 식을 사용하면 \(\sum_{k=1}^{n}{F_k}^2\)를 간단하게 만들 수 있다. \(\sum_{k=1}^{n}{F_k}^2\)에서 \({F_k}^2\)은 위의 식을 이용하여 \(F_k(F.. 2023. 4. 7. 이전 1 다음