[Kotlin] 백준 2086 : 피보나치 수의 합

문제 링크

2086번: 피보나치 수의 합

---

문제 해설

피보나치 수의 성질을 이용하면 쉽게 풀 수 있는 문제다. 기본적으로 \(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}^n (F_{k+2}-F_{k+1})$$

 

덧셈과 뺄셈이 번갈아가며 반복되는 식이므로 중간 항은 모두 정리가 가능하다. 위 식을 전개해보면 다음과 같은 식을 얻을 수 있다.

$$\begin{align*}\sum_{k=1}^{n}(F_{k+2}-F_{k+1})&= F_3-F_2+F_4-F_3+F_5-F_4+\cdots+F_{n+2}-F_{n+1}\\&= F_{n+2}-F_2\\&= F_{n+2}-1\end{align*}$$

 

이제 \(n\)번째 피보나치 수까지의 합을 쉽게 구할 수 있게 되었다. \(a\)번째 피보나치 수부터 \(b\)번째 피보나치 수까지의 합은 \(b\)번째 피보나치 수까지의 총합에서 \(a-1\)번째 피보나치 수까지의 총합을 빼면 구할 수 있다. 즉, 문제에서 요구하는 답은 \(F_{b+2}-1-(F_{a-1+2}-1)=F_{b+2}-F_{a+1}\)이 된다.

 

다만 피보나치 수를 구할 때 나머지를 구하기 때문에 뺄셈 연산을 하면 음수가 나올 수 있다. 예를 들어 \(1,000,000,001-999,999,999=2\)이지만, 각 항을 \(1,000,000,000\)으로 나눈 나머지로 계산하게 되면 \(1-999,999,999=-999,999,998\)이 된다. 따라서, \(F_{b+2}-F_{a+1}\)에 \(1,000,000,000\)을 더해준 후 다시 \(1,000,000,000\)으로 나눠줘야 한다.

 

추가적으로 입력의 최대치가 \(9\times10^{18}\)으로 매우 크기 때문에 [Kotlin] 백준 11444 : 피보나치 수 6에서 사용한 도가뉴 항등식을 사용하여 피보나치 수를 구한다.

Code

fun main() = print(readln().split(' ').map { it.toLong() }
    .let { fibonacci(it[1] + 2) - fibonacci(it[0] + 1) + 1000000000 } % 1000000000)

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)) % 1000000000)
            .also { memory[n] = it }
    }
}