[LeetCode] 746. Min Cost Climbing Stairs

https://leetcode.com/problems/min-cost-climbing-stairs/

Min Cost Climbing Stairs - LeetCode

Min Cost Climbing Stairs - Easy

계단의 칸마다 오르는데 소모되는 비용이 배열로 주어진다.

우리는 가장 아래칸 (-1 인덱스에 있다고 생각하자) 에서 출발을 하는데,

계단은 한칸 또는 두칸을 오를 수 있다.

이때 꼭대기 까지 가는데 드는 최소비용을 구하는 문제다.

 

dp 문제라고 바로 떠올리면 좋다.

dp 배열을 i칸에 도달했을때 드는 최소비용 이라고 생각하고 식을 세우자.

i칸에 도달을 하기 위해서는 i-1칸이나 i-2칸에서 올라야한다.

둘다 현재의 비용에서 i칸만큼의 비용을 내야하므로,

i칸에서의 cost는 i-1칸까지의 cost + cost[i]나 i-2칸 까지의 cost + cost[i] 가 될 것이다.

가장 아래부터 dp식을 잘 세워 왔다면, 이 값은

dp[i-1] + cost[i] 나 dp[i-2] + cost[i] 가 될 것이고, 최소값을 구해야하므로

dp[i] = min(dp[i-1] + cost[i], dp[i-2] + cost[i]) 로 식을 세워주면 된다.

 

전체 풀이 코드

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        if (!cost.size()) return 0;
        if (cost.size()==1) return cost[1];
        int dp[1005] = {INT_MAX};
        dp[0] = 0, dp[1] = cost[0];
        for (int i=1; i<cost.size(); i++) dp[i+1] = min(dp[i]+cost[i], dp[i-1]+cost[i]);
        return min(dp[cost.size()], dp[cost.size()-1]);
    }
};