746. Min Cost Climbing Stairs ★

746. Min Cost Climbing Stairs

 

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        cost.append(0)

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

        return min(cost[0], cost[1])

 

https://youtu.be/ktmzAZWkEZ0?si=ovGzSVLU3LhGRQGh

 

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 꼭대기를 0으로 설정하기 위해 cost 리스트에 0을 추가합니다.
        # 이렇게 하면 마지막 계단에서 꼭대기로 이동하는 추가 비용을 처리하지 않아도 됩니다.
        # 예: 입력이 [10, 15, 20]이라면, cost는 [10, 15, 20, 0]이 됩니다.
        cost.append(0)

        # 뒤에서부터 앞으로 최소 비용을 계산하기 위한 루프
        # len(cost) - 3부터 시작하는 이유:
        # - len(cost) - 1: 꼭대기 (0) -> 이미 정의됨
        # - len(cost) - 2: 마지막 계단 -> 이미 최소 비용 계산 가능
        # - len(cost) - 3부터 계산해야 두 계단 뒤까지의 비용을 참조할 수 있음
        for i in range(len(cost) - 3, -1, -1):
            # 현재 계단에서 최소 비용 계산
            # i 계단의 비용 + (i+1 또는 i+2 계단 중 더 적은 비용)
            # 이 값은 i 계단에서 꼭대기까지 올라가는 최소 비용이 됩니다.
            cost[i] += min(cost[i + 1], cost[i + 2])

        # 첫 번째 계단(cost[0])과 두 번째 계단(cost[1]) 중 더 적은 비용 반환
        # 왜냐하면 시작 위치는 첫 번째 계단 또는 두 번째 계단 중 하나로 자유롭게 선택할 수 있기 때문입니다.
        return min(cost[0], cost[1])

        # 전체 알고리즘의 핵심:
        # - 뒤에서부터 앞으로 거슬러 올라가며, 각 계단에서 최적의 선택을 누적 계산
        # - 모든 계단에서 꼭대기까지의 최소 비용을 구한 후, 시작점이 첫 번째 계단과 두 번째 계단일 때의 최소 비용 반환

3차: 2025.01.02(목) : 아직 한번에 안풀림

 

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 마지막 인덱스 가지전 1칸 또는 2칸 갈수 있음
        # 그래서, 2칸 전인 지점부터..계산하면..
        
        for i in range(len(cost)-1-2, -1, -1):
            cost[i] += min(cost[i+1], cost[i+2])

        # 계산 끝나면. 마지막 2개 중 최소값 return 
        return min(cost[0], cost[1])