[LeetCode] Min Cost Climbing Stairs

https://leetcode.com/explore/challenge/card/june-leetcoding-challenge-2021/603/week-1-june-1st-june-7th/3770/

Explore - LeetCode

 

비용이 담겨 있는 배열을 가지고 있고, 1 혹은 2만큼 이동할 수 있는데 이를 조합하여 최소한의 이동 비용을 구하면 되는 것이다. 

예를 들어서 아래와 같은 배열이 있다고 해보자. 

 

 

시작은 index 0, 1에서 가능하기 때문에 처음에 저장해둔다. 

(DP니까 이제 0,1 경우 저장하는 것은 익숙하게 해줘야 한다!!)

 

위 배열일 경우 최소한의 비용은 어떻게 구할 수 있을까?

요리조리 1, 2 Step 이동해보면 아래와 같은 경우가 가장 최소한의 비용으로 마지막까지 이동할 수 있는 케이스라는 것을 알 수 있다. 

최소 비용

그렇다면 위 과정은 어떻게 구성되어 있는 것일 까?

 

수식으로 보자면 cost[i] = min(cost[i-2], cost[i-1]) + cost[i] (i > 1)이 된다. 

하나씩 풀어서 봐보자. 

앞서 봤듯이 1칸 혹은 2칸 이동이 가능하기에 이 두 개의 선택지 중에서도 최소한의 값을 선택해야한다. 

즉 이 부분이 min(cost[i-2], cost[i-1])가 되는 것이다. 

 

그리고 이동한 칸의 값은 무조건 더해줘야 한다. (+ cost[i] )

가장 최소 비용인 이동 과정을 일부 나타내보면 다음과 같다. 

 

첫 번째

두 번째

세 번째

네 번째

다섯 번째

 

목표는 배열을 벗어나는 경우이기 때문에 마지막, 마지막 - 1 요소를 비교해줘야 한다.

왜냐? 총 2칸까지 이동 가능하기에 마지막 - 1에 위치해도 2칸 이동하면 배열을 벗어날 수 있기 때문이다. 

그렇기에 결과는 min(cost[n-1], cost[n-2]) (n = 배열의 길이) 가 된다. 

 

바로 코드로 가보자. 

 

class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int {
        // cost 총 길이
        let n = cost.count
        // dp 과정을 담을 배열
        var arr = Array(repeating: 0, count: n)
        
        // 초깃값 설정
        arr[0] = cost[0]
        arr[1] = cost[1]
        
        // 2부터 시작 
        // i-1과 i-2중 작은 값과 i를 더해줌 
        for i in 2..<n {
            arr[i] = min(arr[i-1],arr[i-2]) + cost[i]
        }
              
        // 마지막, 마지막 - 1 중에서 최솟값
        return min(arr[n-1], arr[n-2])
    }
}

 

위에서 설명한 부분들이 코드에 담겨있는 것을 볼 수 있다. 

 

배열에서 이동 가능한 경우에 대해 최소 비용들을 구하고 마지막, 마지막-1 부분에서 최솟값을 구하는게 핵심인 문제이다.

말이 조금 헷갈리는데.... 모든 배열의 원소들에 대해 조건에 맞게 이동했을 때 얻어지는 배열을 구하고 그 배열에서 마지막, 마지막-1 중 최솟값을 리턴하면 된다는 이야기..!