[LeetCode] 746. Min Cost Climbing Stairs

말하는 감자·2024년 11월 20일

dynamic programming leetcode python 동적 프로그래밍 리트코드 코딩테스트 코딩테스트 준비 파이썬

LeetCode

목록 보기

13/32

어제 문제 Climbing Stairs와 유사한 문제입니다!! 오늘도 공부해 봅시다.

1. 오늘의 학습 키워드

Dynamic Programming
Top-Down
Bottom-Up

2. 문제: 746. Min Cost Climbing Stairs

단계: Easy
주제: Array, Dynamic Programming
출처: https://leetcode.com/problems/min-cost-climbing-stairs/description/

Description

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

Constraints:

2 <= cost.length <= 1000
0 <= cost[i] <= 999

3. 문제 풀이

계단이 있습니다. 한 번 올라갈 때마다 1 step 또는 2 steps 올라갈 수 있습니다. 문제에서 정수형 배열 cost가 주어지는데, cost[i]는 i번째 계단을 밟았을 때 지불해야 하는 비용입니다. 처음 출발은 index 0 또는 index 1중 한 곳에서 시작할 수 있습니다.

이 계단의 꼭대기에 도착하기 위해 지불해야 하는 최소 비용을 반환해야 합니다.

이 문제의 핵심은 계단을 오를때 1 step 또는 2 steps을 오를수 있다는 점입니다. 계단을 오르면서 해당 위치의 비용을 확인해야 합니다.

그럼 단계를 밟아가보며 문제를 풀어봅시다!

Step1. 문제 이해하기

Input:
- 정수 배열 cost의 길이는 2 이상 1000이하 입니다. 2 이상이라는 것은 첫 출발에서 1 step 또는 2step을 해야하기 때문입니다.
- 1000이하이기 때문에 $O(n^2)$ 까지의 시간복잡도로 코드를 구현해도 될 것 같습니다.
Output:
- 최소 비용을 반환합니다.

cost[i]는 i번째 계단을 밟았을 때 지불해야 하는 비용입니다. 그리고 계단을 올라갈 때 1칸 또는 2칸 올라갈 수 있습니다. 그리고 원하는 output은 꼭대기까지 오르는데 드는 최소 비용입니다.

이 내용을 구현하는데 시간 복잡도는 $O(n^2)$ 까지 가능합니다. 딱 떠오르는 경우는 일단 완전 탐색입니다.

모든 경우를 생각해보는 것이죠! 문제 분석에서 진행해 보겠습니다.

Step2. 문제 분석하기

첫 번째 예시를 보시죠!

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

여기서 말하는 꼭대기는 cost 배열의 마지막 인덱스 + 1 지점을 의미합니다. 즉, 배열의 마지막 계단을 넘어서는 지점이 우리가 도착해야 할 목표입니다. 이를 시각화해 보면, 계단을 오르기 위해 최소 비용을 계산할 때 각 단계에서 선택할 수 있는 경로가 보입니다.

계단은 1 step 또는 2 steps을 올라갈 수 있습니다. 이 뜻은 꼭대기의 1칸, 2칸전까지의 비용을 보면 꼭대기까지 가는데 알 수 있다는 것이죠. 이것을 통해 떠오르는 것이 있습니다. 바로 재귀 함수를 활용하는 것입니다. 다른 예시를 한 번 더 보겠습니다.

이전 예시와 동일하게 꼭대기로부터 1칸, 두 칸 전의 결과를 보고 또 그 1칸, 2칸으로부터 1칸 2칸을 보는식입니다. 또 하나 알 수 있는 것은 재귀를 하면서 중복적으로 계산이 되는 것이 있는 것을 알 수 있습니다.

그렇다는 것은 !! 바로 동적 프로그래밍의 메모이제이션을 사용하면 된다는 것을 알아차릴 수 있습니다.

재귀를 활용한 완전 탐색으로 시작했지만 결국 이 문제는 동적 프로그래밍으로 더 효율적으로 구현할 수 있다는 것을 알게 되었습니다.

재귀 함수를 활용하면 $o(2^n)$ 의 시간복잡도가 나옵니다. 하지만 동적 프로그래밍을 사용하면 $o(n)$ 의 시간 복잡도가 나오게 됩니다.

이제 코드 구현을 하러 갈까요?

Step3. 코드 설계

Base case는 n == 0 or n== 1인 경우입니다. 이 경우에는 0을 반환합니다.
계단은 한 번에 1칸 또는 2칸 올라갈 수 있습니다.
꼭대기에 도달하기 위해, 우리는 꼭대기 전 1칸 전과 2칸 전까지의 최소 비용을 계산하여 결정할 수 있습니다.
이를 통해 점화식을 정의할 수 있습니다:
$dp(n)=min(dp(n−1)+cost[n−1],dp(n−2)+cost[n−2])$

코드 구현을 해보겠습니다.

Step4. 코드 구현

Top-Down

class Solution(object):
    # Top-Down
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        memo = {}
        
        def dp(n):
            if n == 0 or n == 1:
                return 0
            if n in memo:
                return memo[n]
            memo[n] = min(dp(n - 1) + cost[n - 1], dp(n - 2) + cost[n - 2])
            
            return memo[n]
        
        return dp(len(cost))

코드 설명:

Base case: 계단의 시작점(0 또는 1번 인덱스)에서 비용은 없습니다.
재귀 호출: dp(n-1)과 dp(n-2)를 계산하고, 각 계단까지 도달하는 최소 비용을 비교하여 결과를 메모이제이션 테이블에 저장합니다.
최종적으로 len(cost)번째 계단에 도달하기 위한 최소 비용을 반환합니다.

시간 복잡도:

메모이제이션을 통해 각 계단(n)을 한 번만 계산합니다.
각 호출에서 상수 시간(O(1))에 min() 연산을 수행하므로 전체 시간복잡도는 O(n)입니다.

결과:

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

Top-Down으로 문제를 푼다면 Bottom-Up으로도 문제를 풀 수 있어야 합니다! 아래 Bottom-Up 코드입니다.

Bottom-Up

class Solution(object):
# # Bottom-Up
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        n = len(cost)
        dp = [0] * (n + 1)

        for i in range(2, n + 1):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        
        return dp[n]