[99클럽 코테 스터디] 40일차 TIL DP

 

 

오늘의 문제는 LeetCode

 

746. Min Cost Climbing Stairs

 

 

문제

 

 

 

문제 설명 

계단의 각 단계마다의 비용이 배열로 주어지고 한 번에 한 계단 또는 두 계단을 올라갈 수 있다고 했을 때 시작 지점 인덱스는 0 또는 1입니다. 이때  계단을 올라가는데 드는 최소 비용을 찾는 문제입니다. 

 

[입력 예시]

cost = [10,15,20]

[출력 예시]

15

 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 37분이 걸렸습니다.

 

 

 

문제 접근 방식

시작 인덱스가 0 또는 1이기 때문에 최소 비용을 저장할 배열의 0과 1번째 인덱스를 0으로 초기화합니다. 그 다음 주어진 배열을 순회하며 점화식을 계산합니다. 

이때 점화식은 각 계단에서의 한 계단을 오르는 경우와 두 계단을 오르는 경우를 비교해 더 적은 비용이 드는 것을 선택하는 방식으로 계산이 이루어집니다. 

 

 

 

문제 풀이

class Solution {
    public int minCostClimbingStairs(int[] cost) {

        int len = cost.length;
        int[] minCost = new int[len + 1];  

        minCost[0] = 0; 
        minCost[1] = 0; 
    
        for (int i = 2; i <= len; i++) {
            minCost[i] = Math.min(minCost[i - 1] + cost[i - 1], minCost[i - 2] + cost[i - 2]);
        }

        return minCost[len];  
    }
}

 

 

동적 계획법 점화식 찾기 

i번째 계단에 도달하는 방법에는 두 가지가 있습니다. 

 

1. 한 계단만 올라가는 경우 

이 경우엔 인덱스 i-1에서 i로 이동할 때의 비용이 cost[i-1] 이 됩니다. 

 

2. 두 계단을 올라가는 경우 

이 경우, 인덱스 i-2에서 i로 이동할 때의 비용이 cost[i-2]가 됩니다. 

 

따라서 인덱스 i까지의 최소 비용 minCost는 다음과 같은 점화식을 갖습니다. i-1 번째 계단에서 오는 경우와 i-2번째 계단에서 오는 경우 중에 더 비용이 적은 쪽을 선택하는 방식입니다. 

minCost[i] = Math.min(minCost[i - 1] + cost[i - 1], minCost[i - 2] + cost[i - 2]);

 

 

 

 

 

 

 

 

 

이렇게 오늘 40일차 TIL을 작성해 보았습니다.