[Kotlin] 백준 11440 : 피보나치 수의 제곱의 합

문제 링크

11440번: 피보나치 수의 제곱의 합

---

문제 해설

입력의 최대치가 \(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_{k+1}-F_{k-1})=F_kF_{k+1}-F_kF_{k-1}\)로 치환할 수 있다. 즉, \(\sum_{k=1}^{n}{F_k}^2=\sum_{k=1}^{n}(F_kF_{k+1}-F_kF_{k-1})\)가 된다. 이를 전개해보면 다음과 같은 식이 된다.

$$\sum_{k=1}^{n}{F_k}^2=\sum_{k=1}^{n}(F_{k+1}F_k-F_kF_{k-1})=(F_2F_1-F_1F_0)+(F_3F_2-F_2F_1)+(F_4F_3-F_3F_2)+\cdots +(F_{n+1}F_n-F_nF_{n-1})$$

 

위의 전개한 식에서 \(F_{n+1}F_n-F_1F_0\)를 제외한 모든 항은 정리할 수 있다. 즉, \(\sum_{k=1}^{n}{F_k}^2=F_{n+1}F_n-F_1F_0\)이 된다.

 

마지막으로, \(F_0=0\)이기 때문에 \(n\)번째 피보나치 수의 제곱을 합한 값은 다음과 같이 정리된다.

$$\sum_{k=1}^{n}{F_k}^2=F_{n+1}F_n$$

 

이제 \(n\)이 주어지면 2개의 피보나치 수만 구해서 곱하면 된다. \(n\)번째 피보나치 수 \(F_n\)을 구하는 것은 [Kotlin] 백준 11444 : 피보나치 수 6과 같은 방법으로 도가뉴 항등식을 사용하여 구하면 된다.

Code

fun main() = print(readln().toLong().let { (fibonacci(it) * fibonacci(it + 1)) % 1000000007 })

private val memory = HashMap<Long, Long>().also {
    it[0] = 0
    it[1] = 1
}

private fun fibonacci(n: Long): Long {
    return memory[n] ?: run {
        val isEven = n % 2 == 0L
        val f_n = fibonacci(n / 2)
        val f_m = fibonacci(n / 2 + if (isEven) -1 else 1)
        ((if (isEven) (f_n * (2 * f_m + f_n)) else (f_n * f_n + f_m * f_m)) % 1000000007)
            .also { memory[n] = it }
    }
}