[백준] 2579번: 계단 오르기 - Kotlin[코틀린]

문제

 

2579번: 계단 오르기

 

---

풀이

 

 점화식을 만들기 위해 문제에서 주어진 규칙을 보면,

 

 1. 계단은 한번에 한 계단, 두 계단씩 오를 수 있다.

 2. 연속된 3개의 계단을 밟으면 안된다.

 

 이 규칙에서 현재 계단 N을 밟기 위한 방법으로는 N - 2에서 N까지 두 계단 이동한 경우와 N - 3에서 N - 1까지 두 계단 이동하고 N - 1에서 N까지 한 계단 이동한 경우로 2가지만 가능하다.

 연속해서 3개의 계단을 밟는 것이 불가능하기 때문에 위의 두 가지 방법이 전부가 된다. 그렇다면 현재 계단에서의 점수의 최대값은 위의 두가지 방법 중 더 큰 경우의 수 더하기 현재 계단의 값이 된다. 따라서 점화식은 dp[N] = max(dp[N - 2], dp[N - 3] + arr[ - 1]) + arr[N] 이 된다.

 

 첫번째 계단과 두번째 계단은 무조건 밟는 경우가 최대값이기 때문에 각각 값을 대입해두고 반복문을 통해 dp 계산을 하면 된다.

 

---

코드

 

import kotlin.math.*

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

    val num = br.readLine().toInt()
    val dp = IntArray(num+1)
    val arr = IntArray(num){ br.readLine().toInt() }

    dp[1] = arr[0]
    if(num > 1) { // num에 1이 입력될 수 있기 때문에 예외처리 해준다.
        dp[2] = arr[0] + arr[1]
    }
    for(i in 3 .. num) {
        dp[i] = max(dp[i - 2], dp[i - 3]+ arr[i - 2]) + arr[i - 1]
    }

    bw.write("${dp[num]}")
    bw.flush()
    bw.close()
    br.close()
}