min cost climbing stairs

LeetCode - The World's Leading Online Programming Learning Platform

문제 파악 [필수 작성]

문제이해

0번째칸이나 1번째칸에서 출발할 수 있음
각 칸에서의 비용을 내고 1칸이나 2칸 갈 수 있음
끝까지 가는데 최소비용을 구하는 문제

제한 조건 확인

길이는 2~1000

아이디어

[1차 아이디어]
cost 끝에 -1 두개 추가
case1: 0번째 위치에서 출발 1번
case2: 1번째 위치에서 출발 1번
현재 내 위치에서 바로 앞칸과 그다음칸 중 더 비용이 싼곳으로 이동해야함, 가격이 같으면 더 멀리 갈수있는걸로
끝까지 갈때까지 반복 후 case1 과 case2를 비교
-> 이 아이디어로는 [10,15,20,19] 문제를 풀 수 없음
즉, 대소비교가 기준이 되어서는 안됨

[2차 아이디어]
각 칸의 누적합으로 접근 가능하지 않을까?
각 칸에 도달할 수 있는 최소비용으로 접근
n번째 칸은 n-1번째칸과 n-2번째칸 중 더 싼값과 n번째 칸을 더해서 n번째 칸의 누적합을 업데이트
누적합이 다 업데이트 되면, 마지막번째와 마지막번째-1 번째 원소를 비교해서 최소값을 리턴

시간복잡도

O(n)

자료구조

접근 방법 [필수 작성]

아이디어

코드 구현 [필수 작성]

2차 아이디어 (소요시간 15분)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if len(cost) == 2:
            return min(cost[0],cost[1])

        for idx,val in enumerate(cost):
            if idx < 2:
                continue
            cost[idx] = val + min(cost[idx-1],cost[idx-2])
        
        return min(cost[-1],cost[-2])

배우게 된 점 [필수 작성]

자유 형식

질문 [ 필수 X ]

댓글로 또는 이곳에 질문 남겨주세요.