[leetcode] Min Cost Climbing Stairs

Min Cost Climbing Stairs

나의 접근법

종이에 써가면서 봐도 도무지 풀이법을 떠올리지 못했다.

다른 사람 풀이

O(N), O(N) space

앞에 있는 cost 2칸 중 작은 값을 더하면 된다. 더해진 값을 지나오는 것이다. 화살표는 값에 영향을 받았다는 뜻이다.

마지막으로 값을 결정할 땐 맨 마지막이나 그 직전에 도착하면 되기 때문에 둘 중에 작은 값을 리턴한다.

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(2, len(cost)):
            cost[i] += min(cost[i-1], cost[i-2])
        
        return min(cost[-1], cost[-2])

O(N), O(1) space

cost 배열에 값을 저장하지 않고 최솟값을 구하기 위해서는 이전에 나온 값이 무엇이었는지 저장해 주는 변수 2개가 있으면 된다. 루틴은 같고 변수를 사용한 것만 다르다.

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        twoSpacesAgoValue, oneSpaceAgoValue = 0, 0
        
        for i in range(len(cost)):
            currentValue = cost[i] + min(twoSpacesAgoValue, oneSpaceAgoValue)
            twoSpacesAgoValue = oneSpaceAgoValue
            oneSpaceAgoValue = currentValue
        
        return min(twoSpacesAgoValue, oneSpaceAgoValue)

참고 자료

Nick White