[백준][KOTLIN] 1003 피보나치 함수

1003번: 피보나치 함수

풀이

1. 피보나치 수열을 재귀를 이용하여 풀 경우 시간 초과가 발생한다.
2. 동적 프로그래밍(dp) 알고리즘을 이용하여 시간 초과를 해결 한다.
3. 2차원 Int 배열을 선언한다.
4. dp[n][0] 에 0이 나오는 횟수를 저장한다.
5. dp[n][1] 에 1이 나오는 횟수를 저장한다.

코드

import java.util.*

private val dp = Array(41) { IntArray(2) }

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val T = sc.nextLine().toInt()

    // 초기 dp 값
    dp[0][0] = 1 // n이 0일 때 0의 횟수
    dp[1][1] = 1 // n이 1일 때 1의 횟수

    repeat(T) {
        val n = sc.nextLine().toInt()

        for (i in 2..n) {
            dp[i][0] = dp[i - 1][0] + dp[i - 2][0]
            dp[i][1] = dp[i - 1][1] + dp[i - 2][1]
        }

        // 결과 출력
        println("${dp[n][0]} ${dp[n][1]}")
    }
}