백준 2579 계단 오르기 코틀린

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

2579번: 계단 오르기

 

fun main() {
    val n = readLine()!!.toInt()
    val arr = IntArray(n+1) { 0 }
    val dp = Array(n+1) { IntArray(3) { 0 } }

    for (i in 1 until n+1) {
        arr[i] = readLine()!!.toInt()
    }

    dp[1][1] = arr[1]

    for (i in 2 until n + 1) {
        dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + arr[i]
        dp[i][2] = dp[i-1][1] + arr[i]
    }

    val answer = max(dp[n][1], dp[n][2])

    println(answer)
}

점화식 접근 방법으로는

계단을 오르기 위해서는 연속 3회이상 계단을 밟을 수 없기에

이전 계단을 밟거나 밟지 않고 2칸 점프해서 오는 두가지 경우밖에 없다.

이전 계단을 밟았을 경우에는 이전 경우에 수에 현재 계단의 값을 더해주면 되고

2칸을 점프 하여 현재 계단을 밟았을 경우에는 이전 경우의 수(연속으로 밟았거나 한번만 밟았거나) 중 최댑값에 현재 값을 더해주면 된다.