[백준/코틀린] 1003번: 피보나치 함수

링크

1003번: 피보나치 함수

풀이

fibonacci(n) 호출 시 출력되는 0과 1의 개수도 피보나치 수열을 따릅니다.

• 0의 개수 = fibonacci(n-1)에서의 0 개수 + fibonacci(n-2)에서의 0 개수
• 1의 개수 = fibonacci(n-1)에서의 1 개수 + fibonacci(n-2)에서의 1 개수

피보나치 수열을 재귀적으로 구현하고, 메모이제이션을 사용하여 중복 계산을 방지합니다.

코드

val fibonacciCache = MutableList(41) { -1 }
fun fibonacci(n: Int): Int {
    if (n == -1) return 1
    if (fibonacciCache[n] != -1) return fibonacciCache[n]

    return when (n) {
        0 -> 0
        1 -> 1
        else -> fibonacci(n - 1) + fibonacci(n - 2)
    }.also { fibonacciCache[n] = it }
}

fun main() = repeat(readln().toInt()) {
    val n = readln().toInt()

    println("${fibonacci(n - 1)} ${fibonacci(n)}")
}