swift ) Leetcode - 746. Min Cost Climbing Stairs

면접에서 마주한 문제

....ㅠㅠ 로직 생각하고 구현을 어떻게 시작할지 한참 고민 끝에.. 무지성으로 만들다가 생각나버린..

아.. 이거 dp구나 싶은 순간

응 코테 종료할게요

알고리즘 열심히 하겠습니다...

눈만 마주쳐도 아.. 이거 dp구나 할 수 있도록..

 

- 처음 생각한 접근방식 

인덱스 0 / 1에서 시작하는 경우를 각각 고려해서

바로 다음 칸 / 두 번째 뒤의 칸의 cost와 각각 비교하여 최소값이 나오는 방향으로 나아감

-> 여기서 발상이 조금 더 나갔어야 했는데.. 아쉬웠다.

 

 

- DP 활용(Bottom Up DP)

class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int {
        var dp = cost
        let n = dp.count
        
        for i in 2..<n {
            dp[i] += min(dp[i - 1], dp[i - 2])
        }
        
        return min(dp[n - 1], dp[n - 2])
    }
}

 

각각의 계단에 도달하는 최소 비용이 들어갈 dp 배열을 하나 만들어주고,

loop 안에서 계산해줌.

모든 계단에 대해 각각 필요한 최소비용을 구할 수 있게 되고,

마지막 계단에 도달하는 데 필요한 최소비용을 최종적으로 반환하게 됨.