746. Min Cost Climbing Stairs (Easy) [Python]

문제

생각 방식

dp문제 유형이다

Minimum cost를 구하는 문제이므로 for loop으로 dp에 최솟값을 저장해 주면 된다

 

풀이 과정

1번째 계단이나 2번째 계단에 도달하는 cost는 0이다

dp[0] = dp[1] = 0

왜? 시작을 index 0이나 1 아무 곳에서 시작해도 된다고 하니까

 

그러므로 index[2]부터 저장을 시작해 주면 된다

그래서 2에서 loop을 시작하면 될 것이고, cost의 마지막까지 돌려주는 걸 loop의 조건으로 해주면 될 것이다

 

* for loop안에는 뭘 작성해야하는가?

당연힌 말이지만 dp에 저장을 값을 저장하는 코드를 짜주면 된다

 

한 번에 one or two steps를 갈 수 있다고 문제에 나와있다

그럼 2번째 계단( i=3)을 가는데 그럼 어떤 방식이 있는가?

1. 0번째 계단에서 2 steps

2. 1번째 계단에서 1 step 

그렇다면 우리는 둘 중에 최솟값만 dp에 저장해 주면 될 것이다

 

 

💻 작성 코드

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        c = len(cost)
        dp = [0] * (c+1)

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

        return dp[c]

 

 

* dp[i-1] + cost[i-1] 그리고 dp[i-2] + cost[i-2] 에 대한 설명

그림으로 그리는 게 기억에 더 남으니까 그림으로 한 번 설명을 해보겠다

 

i = 2일 때, 2번 계단으로 도착하는 방법은 2가지가 존재한다 (그림 참고)

0번째 계단에서 2번째 계단으로 가는 cost는 10

1번째 계단에서 2번째 계단으로 가는 cost는 15

이 두 가지 방법 중에 가장 적은 cost를 사용하는 건 10 즉 첫 번째 방법이기에 10을 dp[2]에 저장해 준다

 

마찬가지로 i = 3일 때,

1번 계단에서 3번 계단에 도달하기 위한 cost는 얼마? 15

2번에서 3번은? 20인데 여기서 2번까지 가기 위한 값도 합쳐줘야 한다.

 

왜? 2번에 원래부터 있을 수 없기 때문에

2로 가는 가장 효율적인 cost는 위에 i = 2일 때 계산한 10이다

 

그럼 10 + 20 해서 30이 나오는데 가장 효율적인 건 15라는 cost가 든다

그래서 dp[3]에는 15 저장하면 된다

 

i = 4일 때는 이 글을 읽는 분이 종이에 직접 한 번 써보시면 이해하는 데 도움이 될 것 같다

 

마지막에 dp[c]로 리턴을 해주는 이유

마지막 dp가 우리가 제일 적은 비용으로 top에 도달할 수 있는 비용이다.

c는 우리가 받은 list의 총 길이이므로 마지막 c는 우리의 마지막 index가 된다.

 

그래서 test case [10,15,20,30]을 넣으면 결과는 dp[4], 즉 30으로 나온다

결과

 

푸는 것보다 이해하는 것이 제일 중요하다

대충 이해하지 말고 진짜 하나하나 왜냐는 질문을 가지고 접근을 하면 느리겠지만 성장은 확실하겠지...?

이해하면 이렇게 문제 푸는 과정이 당연해지고 익숙해질 테니까 열심히 해보자

화이팅 화이팅 화이팅 화이팅 화이팅 화이팅 화이팅 화이팅 화이팅 화이팅 화이팅 화이팅 화이팅 화이팅 화이팅 !