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

문제

 

1003번: 피보나치 함수

 

---

풀이

 

 문제에서 주어진 코드대로 피보나치 수열을 재귀함수로 구현하고, 0과 1을 세는 방법으로 문제를 풀면 시간초과가 발생한다. 대신 DP를 이용해 피보나치 수열을 풀면 된다. 피보나치 수란 한 단계 전의 숫자와 두 단계 전의 숫자를 합한 수의 수열이다. 예를 들어 1, 1, 2, 3, 5, 8 ... 등이 피보나치 수이다. 피보나치 수를 점화식으로 나타내면 dp[n] = dp[n - 1] + dp[n - 2]이다.

 

 이 점화식에서 dp[n - 1] = dp[n - 2] + dp[n  - 3] 이고 dp[n - 2] = dp[n - 3] + dp[n - 4]이므로, dp[n] = (dp[n - 2] + dp[n -3]) + (dp[n -3] + dp[n - 4]) 으로 표현할 수 있다. 똑같은 과정을 통해 단계가 끝까지 내려간 뒤에는 dp[n]을 dp[2] + dp[1] 에서 dp[1] + dp[0] + dp[1]으로 표현할 수 있을 것이다.

 

 이 문제에서 구하고자 하는 것은 0과 1이 호출되는 숫자이다. 입력받은 N의 0과 1의 호출 숫자는 dp[N-1]의 0과 1의 호출 숫자와 dp[N - 2]의 0과 1의 호출 숫자의 합이다. 이 호출 숫자들의 합 또한 최종적으로는 dp[2](dp[1] + dp[0]) + dp[1]의 0과 1의 호출 숫자의 합이 된다.

 

 숫자가 0일 때 호출되는 0은 1번, 1은 0번이고, 숫자가 1일 때 호출되는 0은 0번, 1은 1번, 숫자가 2일 때 호출되는 0은 1번, 1은 1번, 숫자가 3일 때 호출되는 0은 1번, 1은 2번이다. 이와 같은 과정으로 호출 횟수를 합한다면 dp[N]일 때 호출되는 0은 dp[N-1]번, 1은 dp[N]번이 된다.

 

 문제에서 주어진 범위인 40까지 DP의 계산을 미리 해두고, 입력받은 숫자 N의 dp[N - 1]  과 dp[N]을 출력하면 된다. 0을 입력 받은 경우 계산에서 오류가 발생하므로, 1 0을 출력해준다.

 

---

코드

 

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

    val testCase = br.readLine().toInt()

    val dp = IntArray(41)
    dp[1] = 1
    for(i in 2 .. 40) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }

    repeat(testCase) {
        val num = br.readLine().toInt()

        if(num==0) {
            bw.append("1 0\n")
        } else {
            bw.append("${dp[num-1]} ${dp[num]}\n")
        }
    }

    bw.write("")
    bw.flush()
    bw.close()
    br.close()
}