백준 2579번: 계단 오르기 (Kotlin)

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

2579번: 계단 오르기

 

코드

포도주 시식 문제(https://www.acmicpc.net/problem/2156)와 정말 비슷하다.

포도주 시식 포스팅: (https://best-human-developer.tistory.com/19)

 

다른 점이 하나 있는데, 포도주 문제에서는 i번째 포도주를 선택하지 않아도 되지만 계단 오르기에서는 i번째 계단을 반드시 밟아야 한다. i번째 계단을 밟지 않는 경우를 포함시키면 3칸 이상을 건너뛰는 상황이 발생해서, 한 번에 한 계단 또는 두 계단씩만 오를 수 있다는 조건1을 만족시키지 못하기 때문이다.

 

따라서,

함수) dp[i]: i번째 계단까지만 존재할 때, 조건1,2,3을 만족하는 최대 점수

점화식) i번째 계단 + i-1번째 계단을 밟는 경우와 i번째 계단 + i-2번째 계단을 밟는 경우 중 최대 값

-> dp[i] = max( stair[i] + stair[i-1] + dp[i-3] , stair[i] + dp[i-2] ) 

초기값) dp[0] = 1, dp[1] = stair[1], dp[2] = stair[1] + stair[2]

 

와 같이 반복문을 구성하면, 초기 값부터 조건을 만족하면서 모든 경우의 수를 포함하기 때문에 dp[3] ~ dp[n]까지 답을 구할 수 있다.

 

정답) dp[n]

 

풀이

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val stairs = IntArray(n+2)	// n+2: 초기 값 설정할 때 인덱스 에러를 막는다 
    val dp = IntArray(n+2)

    repeat(n) { i ->
        stairs[i+1] = readLine()!!.toInt()
    }

    dp[1] = stairs[1]
    dp[2] = stairs[1] + stairs[2]
    for (i in 3..n){
        // 직전 계단+현재 계단, 두 칸 전 계단+현재 계단 중 최대 값
        // 현재 계단을 밟지 않는 경우도 포함시키면, 세 칸 이상을 뛰어넘는 경우가 발생한다
        dp[i] = max(stairs[i] + stairs[i-1] + dp[i-3], stairs[i] + dp[i-2])
    }

    println(dp[n])
}