피보나치 수3 [Kotlin] 백준 2086 : 피보나치 수의 합 문제 링크 2086번: 피보나치 수의 합 제 1항과 제 2항을 1이라 하고, 제 3항부터는 앞의 두 항의 합을 취하는 수열을 피보나치(fibonacci) 수열이라고 한다. 예를 들어 제 3항은 2이며, 제 4항은 3이다. 피보나치 수열의 a번째 항부터 b번째 www.acmicpc.net 문제 해설 피보나치 수의 성질을 이용하면 쉽게 풀 수 있는 문제다. 기본적으로 \(n\)에 대한 피보나치 수의 점화식은 \(F_n=F_{n-1}+F_{n-2}\)가 되는데 여기서 \(n\)에 \(n+2\)을 대입하고 식을 조금 정리하면 \(F_n=F_{n+2}-F_{n+1}\)이 된다. 이렇게 되면 \(F_n\)까지의 모든 피보나치 수의 합은 다음과 같다고 볼 수 있다. $$\sum_{k=1}^n F_k=\sum_{k=1.. 2023. 4. 10. [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. [Kotlin] 백준 11444 : 피보나치 수 6 문제 링크 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해설 피보나치 수를 구하는 문제지만 입력이 굉장히 큰 경우다. 이 경우 피보나치 수를 구하는 일반적인 식인 \(F_n=F_{n-1}+F_{n-2}\)을 사용하게 되면 최대 \(10^{18}\)번의 연산을 수행해야 하기 때문에 이 방법은 사용할 수 없다. 문제를 해결하기 위해서는 더 효율적인 방법을 찾아야 하는데, 피보나치 수를 구하는 방법 중에는 도가뉴 항등식(d'Ocagne's identity)이라는 것이 있다. 도가뉴 항등식의 형태는 다음과 같다. $$F_{m+n}=F_{m-1}F_n+F_mF_{n+1}$$ 여기서 \(m.. 2023. 1. 24. 이전 1 다음
