[LeetCode] 746. Min Cost Climbing Stairs - 파이썬(Python)

2022. 5. 13. 17:35·Solving Algorithm Problem/LeetCode

문제 링크 : https://leetcode.com/problems/min-cost-climbing-stairs/

 

Min Cost Climbing Stairs - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

유형 : 동적 계획법(Dynamic Programming)

문제 설명

계단을 밟는 비용이 담긴 정수 배열 cost가 주어질 때, 계단 꼭대기에 도달하기 위한 최소 비용을 return 하는 문제이다. 이때, 비용을 지불하면 계단을 1칸 또는 2칸을 오를 수 있고, 0번째 혹은 1번째 계단에서 시작할 수 있다.

Example 1)
Input: cost = [10,15,20]
Output: 15
Example 2)
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6

제한사항

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

문제 풀이

성공 코드

from typing import List

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        total_count = len(cost)
        min_cost = [0] * (total_count+1)
        
        for i in range(2, total_count + 1):
            one_step = min_cost[i-1] + cost[i-1]
            two_step = min_cost[i-2] + cost[i-2]
            min_cost[i] = min(one_step, two_step)

        return min_cost[total_count]

시간 복잡도 : O(n)

공간 복잡도 : O(n)

기본적으로 Memoization 기법을 사용하면 O(n)의 공간복잡도가 필요하지만, 사실상 n-1과 n-2번째 계단의 최소 비용만으로 n번째 계단의 최소 비용을 구할 수 있으므로 시간 복잡도를 O(1)으로 줄일 수 있다.

저작자표시 (새창열림)
'Solving Algorithm Problem/LeetCode' 카테고리의 다른 글
  • [LeetCode] 322. Coin Change - 파이썬(Python)
  • [LeetCode] 64. Minimum Path Sum - 파이썬(Python)
  • [LeetCode] 70. Climbing Stairs - 파이썬(Python)
  • [LeetCode] 39. Combination Sum - 파이썬(Python)
김행만
김행만
이모저모 다 적기
  • 김행만
    hyeinisfree
    김행만
  • 전체
    오늘
    어제
    • 분류 전체보기 (41)
      • AWS (0)
      • Network (6)
      • CICD (1)
      • Spring (0)
      • Ruby on Rails (0)
      • Java (12)
      • Python (1)
      • Computer Science (6)
        • Algorithm (2)
        • Data Structure (3)
        • Database (0)
        • Design Pattern (1)
      • Solving Algorithm Problem (12)
        • LeetCode (12)
        • Programmers (0)
      • 자격증 (1)
      • Tip (1)
      • Etc (1)
        • 도서, 강의 (1)
        • Talk (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • GitHub
  • 공지사항

  • 인기 글

  • 태그

    java
    cisco packet tracer
    Packet Tracer
    Network
    CISCO
    java 필수 문법
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
김행만
[LeetCode] 746. Min Cost Climbing Stairs - 파이썬(Python)
상단으로

티스토리툴바