[Kotiln] 백준 17175 : 피보나치는 지겨웡~

문제 링크

17175번: 피보나치는 지겨웡~

---

---

문제 해설

다이나믹 프로그래밍의 기초가 되는 문제이다. 피보나치 수의 특성 상 \(fibonacci(n)\)을 입력했을 때의 \(fibonacci\) 함수 호출 횟수 또한 이전 \(fibonacci\) 함수의 호출 횟수로 구할 수 있다. \(fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)\)라는 것은 함수 호출 횟수는 마찬가지로 이전 2개의 \(fibonacci\) 함수 호출 횟수를 더한 값 + (\(fibonacci(n)\)을 호출한 횟수\(=1\))이 된다. \(fibonacci(n)\)을 입력했을 때의 \(fibonacci\) 함수 호출 횟수를 \(g(x)\)라고 했을 때 아래의 예시를 보자.

• \(g(0)\) = 1
• \(g(1)\) = 1
• \(g(2)\) = 1 + 1 + 1 = 3
• \(g(3)\) = 1 + 3 + 1 = 5
• \(g(4)\) = 1 + 5 + 3 = 9
• ...

위의 예시와 같이 \(g(n)=1+g(n-1)+g(n-2)\)가 된다. 따라서 호출 횟수의 초기값인 \(g(0)\)과 \(g(1)\)만 1로 초기화를 해주고 정답을 구해나가면 된다.

 

단, \(n\)이 0부터 시작하기 때문에 \(g(1)\)은 \(n\)이 0보다 클 때만 초기화해야 ArrayIndexOutOfBoundsException이 발생하지 않는다.

---

Code

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val dp = IntArray(n + 1)
    dp[0] = 1
    if (n > 0) dp[1] = 1
    for (i in 2..dp.lastIndex) {
        dp[i] = (1 + dp[i - 1] + dp[i - 2]) % 1000000007
    }
    println(dp[n])
}