Baekjoon(Kotlin) - 24416. 알고리즘 수업 - 피보나치 수 1

URL : https://www.acmicpc.net/problem/24416

24416번: 알고리즘 수업 - 피보나치 수 1

 

[ RESULT ]

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))

fun main() {
    val n = br.readLine().toInt()
    val dpCnt = 0

    bw.write("${fibonacci_recursion(n)} ${fibonacci_dp(n, dpCnt)}")

    br.close()
    bw.close()
}

fun fibonacci_recursion(N: Int): Int {
    return if(N == 1 || N == 2) {
        1
    }
    else (fibonacci_recursion(N-1) + fibonacci_recursion(N-2))
}

fun fibonacci_dp(N: Int, cnt: Int): Int {
    val mList = MutableList(N + 1) { 0 }

    mList[1] = 0
    mList[2] = 1

    var dpCnt = cnt

    for (i in 3..N) {
        dpCnt++
        mList[i] = mList[i - 1] + mList[i - 2]
    }

    return dpCnt
}