[Algorithm] 계단 오르기

[hwangJi-dev]

💬 문제

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

💬 Idea

[ 계단 오르기 규칙 ]

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

[ 점화식 ]

3칸 연속으로 계단을 밟을 수 없기 때문에 다음과 같은 점화식이 도출된다.

• max로 도달하며 올라온 계단의 점수합[i - 3] + 계단 점수[i - 1] + 계단 점수[i]
• max로 도달하며 올라온 계단의 점수합[i - 2] + 계단 점수[i]

→ 위 두가지 경우 중 더 큰 값을 **max로 도달해 올라온 계단의 합[i]**에 저장해나간다.

💬 풀이

import Foundation

func solution2579() {
    let N = Int(readLine()!)!
    var stairs = Array(repeating: 0, count: N + 1)
    var maxStairs = stairs
    
    for i in 1...N {
        let n = Int(readLine()!)!
        stairs[i] = n
        
        if i == 1 {
            maxStairs[1] = stairs[i]
        } else if i == 2 {
            maxStairs[2] = maxStairs[1] + stairs[i]
        } else {
            maxStairs[i] = max(maxStairs[i - 3] + stairs[i - 1] + stairs[i], maxStairs[i - 2] + stairs[i])
        }
    }
    print(maxStairs[N])
}