[Leetcode] 746. Min Cost Climbing Stairs

문제 정의 

i번째 step 에 대한 cost 가 들어있는 integer array인 cost가 주어지고, cost를 지불하면 1번 또는 2번의 step을 이동할 수 있다. 0 혹은 1의 인덱스에서 시작할 수 있을 때 top을 가기 위한 최소한의 cost를 구하라.

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

Min Cost Climbing Stairs - LeetCode

 

풀이

보자마자 dp 로 풀면 되겠다고 생각이 들었다.

간단하게 점화식을 세워볼 수 있다. minCost[i] 는 i번째까지 도달하기 위한 최소한의 cost를 담는다.

• i=0 or 1 -> minCost[i] = cost[i]
• i > 1 -> minCost[i] = min(minCost[i-1], minCost[i-2]) + cost[i];

0 혹은 1부터 시작할 수 있다고 하였으니 첫 스탭은 cost[i] 그대로의 값이 최소한의 cost 이다.

minCost[i]에 i번째까지의 최소한의 cost를 구하기 위해서, i로 올 수 있는 방법은 i-1번째 혹은 i-2번째 인덱스에서 올 수 있다. minCost[i-1]에는 i-1번째까지 오기 위한 최소한의 cost가 담겨있고, minCost[i-2]에는 i-2번째까지 오기 위한 최소한의 cost가 담겨있으니 둘 중 작은 값에 cost[i]를 더해주면 i번째까지 오기 위한 최소한의 cost가 계산된다.

최종적으로 원하는 값은 top 까지 가기 위한 최소한의 cost이므로 cost 배열의 가장 끝인덱스 혹은 끝인덱스-1번째의 cost 중 작은 값이 정답이다.

 

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int size = cost.length;
        int[] minCost = new int[size + 1];
        
        minCost[0] = cost[0];
        minCost[1] = cost[1];
        
        for (int i=2; i < size; i++) {
            minCost[i] = Math.min(minCost[i-1], minCost[i-2]) + cost[i];    
        }
        return Math.min(minCost[size-2], minCost[size-1]);
    }
}

 

오랜만에 알고리즘 푸니까 재밌넹 ^0^ ㅎㅎㅎ