[leetcode] 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)
참고 자료
Author And Source
이 문제에 관하여([leetcode] Min Cost Climbing Stairs), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hotbreakb/leetcode-Min-Cost-Climbing-Stairs저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)