[백준/BOJ] 1003번: 피보나치 함수

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

문제

해설

이 문제는 n값에 대한 수열에서 재귀함수의 과정 중 fibonacci(0)과 fibonacci(1)이 몇 번 나오는지 구하는 것이다.

이제 n의 값에 따른 fibonacci(0)과 fibonacci(1)의 출력 횟수의 상관관계에 대해 보겠다.

n	fibonacci(n)	fibonacci(0)	fibonacci(1)
0	0	1	0
1	1	0	1
2	1	1	1
3	2	1	2
4	3	2	3
5	5	3	5
6	8	5	8

표를 보면

fibonacci(0)은 n이 0일 때를 제외하고는 fibonacci(n-1)의 값이 뜨고, fibonacci(1)은 fibonacci(n)과 같은 값이 뜬다.

따라서 다이나믹 프로그래밍 방식으로 값을 미리 구해놓고 n이 입력되었을 때 각각의 출력 횟수를 보이면 된다.

소스 코드

val dp = arrayListOf<Pair<Int, Int>>()

fun main() {
    val testCase = readLine()!!.toInt()
    dp.add(1 to 0)
    dp.add(0 to 1)
    for(i in 2..40) dp.add((dp[i-1].first + dp[i-2].first) to (dp[i-1].second + dp[i-2].second))
    for(i in 0 until testCase){
        val n = readLine()!!.toInt()
        println("${dp[n].first} ${dp[n].second}")
    }
}