Swift) 백준 2579번 계단 오르기 - S3

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

 

계단의 점화식 문제.

특정 계단에서 얻을 수 있는 점수는 다음과 같다.

• n-1, n 이렇게 연속적으로 접근
• n-2, n 이렇게 떨어져서 접근

따라서 다음과 같은 점화식이 세워짐

• dp[i-3]+stair[i-1]+stait[i] (연속적으로 계단에 접근한 경우)
• dp[i-2]+stair[i] (비연속적으로 계단에 접근한 경우)

import Foundation

let n = Int(readLine()!)!
var stairtArr: [Int] = []
for _ in 0..<n {
    let input = Int(readLine()!)!
    stairtArr.append(input)
}
var dp: [Int] = Array(repeating: 0, count: n)
if n == 1 {
    print(stairtArr[0])
} else if n==2 {
    print(stairtArr[0]+stairtArr[1])
} else {
    dp[0] = stairtArr[0]
    dp[1] = stairtArr[0]+stairtArr[1]
    dp[2] = max(stairtArr[0]+stairtArr[2], stairtArr[1]+stairtArr[2])
    for i in 3..<n {
        dp[i] = max(dp[i-2]+stairtArr[i], dp[i-3]+stairtArr[i-1]+stairtArr[i])
    }
    print(dp[n-1])
}