[백준] 2579번: 계단 오르기

문제

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

풀이

• 메모이제이션
• 마지막 계단을 밟아야하므로 dp값에는 해당 인덱스의 step을 더해주고, 마지막 dp의 인덱스를 반환해주어야하 한다.

import kotlin.math.max

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()
    val stepList = mutableListOf<Int>()
    repeat(n) {
        stepList.add(br.readLine().toInt())
    }
    bw.write("${calcMaxStep(stepList)}")
    bw.close()
    br.close()
}

fun calcMaxStep(steps: List<Int>): Int {
    val length = steps.size
    val dp = Array(length) { 0 }
    dp[0] = steps[0]
    if (length == 1) return dp[0]
    dp[1] = dp[0] + steps[1]
    if (length == 2) return dp[1]
    dp[2] = max(steps[0] + steps[2], steps[1] + steps[2])
    if (length == 3) return dp[2]
    for (i in 3 until length) {
        dp[i] = max(dp[i - 3] + steps[i - 1] + steps[i], dp[i - 2] + steps[i])
    }
    return dp[length - 1]
}

더 좋은 풀이 있으면 댓글 달아주세요!!!