[백준] 계단 오르기 (2579)

문제 설명

백준 2579번 문제 링크

입력 및 출력

» 입력

• 입력의 첫째 줄에 계단의 개수가 주어진다. 둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

» 출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입출력(테스트케이스)

입력	출력
6 10 20 15 25 10 20	75
1 10	10
2 10 20	30

문제 풀이 (KOTLIN)

import kotlin.math.max

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val S = IntArray(N + 1)
    val dp = IntArray(N + 1)

    for (n in 1..N) S[n] = readLine().toInt()

    when (N) {
        1 -> println(S[1])
        2 -> println(S[1] + S[2])
        3 -> println(S[3] + max(S[1], S[2]))
        else -> {
            dp[1] = S[1]
            dp[2] = S[2] + S[1]
            dp[3] = S[3] + max(S[1], S[2])

            for (n in 4..N)
                dp[n] = S[n] + max(dp[n - 2], S[n - 1] + dp[n - 3])

            println(dp[N])
        }
    }
}

Debug (KOTLIN)

문제 풀이 (SWIFT)

let N = Int(readLine()!)!
var stair = [Int](repeating: 0, count: N + 1)
var dp = [Int](repeating: 0, count: N + 1)

for i in 1...N {
    stair[i] = Int(readLine()!)!
}

if N >= 1 {
    dp[1] = stair[1]
}

if N >= 2 {
    dp[2] = stair[1] + stair[2]
}

if N >= 3 {
    for i in 3...N {
        dp[i] = max(stair[i] + dp[i - 2], stair[i] + stair[i - 1] + dp[i - 3])
    }
}

print(dp[N])