[LeetCode] [Swift] 746. Min Cost Climbing Stairs

문제

746. Min Cost Climbing Stairs

문제파악하기

계단 하나를 오를 때 마다 비용이 발생하고, 한번에 1 or 2 개의 계단을 오를 수 있다.
[10, 15, 20] 의 계단이 있다면 index 1부터 시작하고 비용 15를 낸 후 2개의 계단을 오르면 최소 비용이된다. (처음에 2개의 계단을 오름)
[1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 의 계단이 있다면 최대한 1을 밟는 경우의 수를 늘려 비용을 절약할 수 있겠다.
그러면 이걸 제약조건을 보면서 생각해보자.

Constraints:

• 2 <= cost.length <= 1000
  주어진 배열의 최소 길이가 2라는 뜻은 loop에서 2-1, 2-2로 에러 없이 확인할 수 있다는 뜻
• 0 <= cost[i] <= 999

풀이

// 746. Min Cost Climbing Stairs
class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int {
        var dp = [Int](repeating: 0, count: cost.count)
        dp[0] = cost[0] 
        dp[1] = cost[1]
        for i in 2 ..< cost.count { // 배열의 최소 길이는 2
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
            // print("dp : \(dp), dp[i] : \(dp[i])")
        }
        let last = cost.count - 1
        return min(dp[last], dp[last-1])
    }
}

🤔 FEEDBACK

코드만으로 출력 값을 유추하기 어려워서 출력해봤다.

dp : [1, 100, 2, 0, 0, 0, 0, 0, 0, 0], dp[i] : 2
dp : [1, 100, 2, 3, 0, 0, 0, 0, 0, 0], dp[i] : 3
dp : [1, 100, 2, 3, 3, 0, 0, 0, 0, 0], dp[i] : 3
dp : [1, 100, 2, 3, 3, 103, 0, 0, 0, 0], dp[i] : 103
dp : [1, 100, 2, 3, 3, 103, 4, 0, 0, 0], dp[i] : 4
dp : [1, 100, 2, 3, 3, 103, 4, 5, 0, 0], dp[i] : 5
dp : [1, 100, 2, 3, 3, 103, 4, 5, 104, 0], dp[i] : 104
dp : [1, 100, 2, 3, 3, 103, 4, 5, 104, 6], dp[i] : 6

즉, dp[i] 값에 최소 비용을 계속 누적해가면서 2칸씩 비교를 한다.
중간에 어떤 큰 값이 나와도 상관없는 이유는 맨 마지막에도 2개의 값을 비교해서 최소값을 결정하기 때문이다.

Reference

• 746. Min Cost Climbing Stairs DP 접근 방법