[백준] 11444번: 피보나치 수 6 - Kotlin[코틀린]

문제

 

11444번: 피보나치 수 6

 

---

풀이

 

 이 문제는 행렬의 거듭제곱을 이용해 피보나치를 구하는 방법으로 해결할 수 있고 구하는 방법은 다음과 같다.

 피보나치 수열을 수식으로 나타내면 $f_{n+2} = f_{n+1} + f_{n}$ 이고, 식을 행렬의 곱으로 나타낼 수 있다.
  $f_{n+2} = f_{n+1} + f_{n} \\         = 1 \times f_{n+1} + 1 \times f_{n} \\         = \begin{bmatrix}1&1\end{bmatrix} \times \begin{bmatrix}f_{n+1} \\ f_{n}\end{bmatrix}$
 2 X 2 행렬을 만들기 위해 $f_{n+1}$을 행렬 곱으로 나타낸다.
  $f_{n+1} = 1 \times f_{n+1} + 0 \times f_{n} \\                  = \begin{bmatrix}1&0\end{bmatrix} \times \begin{bmatrix}f_{n+1} \\ f_{n}\end{bmatrix}$
 이렇게 구한 $f_{n+2}$과 $f_{n+1}$을 행렬로 나타내면 다음과 같은 식을 얻을 수 있다.
  $f_{n+2} = \begin{bmatrix}1&1\end{bmatrix} \times \begin{bmatrix}f_{n+1} \\ f_{n}\end{bmatrix}$
  $f_{n+1} = \begin{bmatrix}1&0\end{bmatrix} \times \begin{bmatrix}f_{n+1} \\ f_{n}\end{bmatrix}$
  $\begin{bmatrix} f_{n+2} \\ f_{n+1} \end{bmatrix} = \begin{bmatrix}1&1 \\ 1&0 \end{bmatrix} \times \begin{bmatrix}f_{n+1} \\ f_{n}\end{bmatrix}$

여기서 $\begin{bmatrix} f_{n+1} \\ f_{n} \end{bmatrix}$를 $S_{n}$, $\begin{bmatrix}1&1 \\ 1&0 \end{bmatrix}$를 A로 치환하고 거듭제곱으로 나타내보면,

  $S_{n+1} = AS_{n}$
  $S_{1} = AS_{0}$
  $S_{2} = AS_{1} = A(AS_{0})$
  $S_{3} = AS_{2} = A(A(AS_{0}))$
   ...
  $S_{n} = A^nS_{0} =\begin{bmatrix}1&1 \\ 1&0 \end{bmatrix}^n\begin{bmatrix} S_1 \\ S_0 \end{bmatrix}=\begin{bmatrix}1&1 \\ 1&0 \end{bmatrix}^n\begin{bmatrix}1 \\ 0 \end{bmatrix}$

  $\begin{bmatrix} f_{n+1} \\ f_{n} \end{bmatrix} =\begin{bmatrix}1&1 \\ 1&0 \end{bmatrix}^n\begin{bmatrix}1 \\ 0 \end{bmatrix}$
  $\begin{bmatrix}1&1 \\ 1&0 \end{bmatrix}^n=\begin{bmatrix}f_{n+1}&f{n}\\f{n}&f{n-1}\end{bmatrix}$

 위의 정리에 따라 행렬을 거듭 제곱하여 피보나치 수를 구하면 된다. 행렬의 거듭제곱은 10830번 행렬 제곱처럼 분할 정복을 이용하면 된다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toLong()
    val origin = arrayOf(longArrayOf(1L, 1L), longArrayOf(1L, 0L))

    bw.write("${power(origin, num-1)[0][0]}")
    bw.flush()
    bw.close()
    br.close()
}

fun multi(st: Array<LongArray>, origin: Array<LongArray>): Array<LongArray> {
    val tmp = Array(2) { LongArray(2) }
    for (i in 0 until 2) {
        for (j in 0 until 2) {
            for (k in 0 until 2) {
                tmp[i][j] += st[i][k] * origin[k][j]
            }
            tmp[i][j] %= 1000000007L
        }
    }
    return tmp
}

fun power(mat: Array<LongArray>, exponent: Long): Array<LongArray> {
    return when(exponent) {
        0L, 1L -> mat
        else -> {
            val n = power(mat, exponent / 2)

            if (exponent % 2 == 0L) multi(n, n)
            else multi(multi(n, n), mat)
        }
    }
}