70. Climbing Stairs (Easy) [Python]

문제

 

생각 방식

일단 수학적으로 생각을 해봤다

n = 0, res = 0 ----> [dp에 저장할 때는 1로 저장함, 설명은 밑에 있음]

n = 1, res = 1

n = 2, res = 2

n = 3, res = 3

n = 4, res = 5

n = 5, res = 8

 

이걸 보자마자 Fibonacci가 떠올랐다

Fibonacci Sequence:

F(n) = F(n-1) + F(n-2)

F(0) = 0, F(1) = 1  -----> base case

 

피보나치는 전형적인 dp문제 유형이다

 

그러므로 array를 길이 n+1만큼으로 잡아주고 for loop으로 값을 저장해주면 될 것 같다

 

💻 작성 코드

 

class Solution:
    def climbStairs(self, n: int) -> int:
        
        if n < 2:
            return n
        
        dp=[0]*(n+1)

        dp[0] = 1
        dp[1] = 1
        
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n]

 

⭐️ 여기서 왜 dp[0] = 1이냐?

n = 0, dp[0] = 0 이 맞는 게 아닌가라는 생각이 들 수 있다.

이렇게 설정한 이유는 우리가 계단에 도착하는 걸음수가 아니라 도달할 수 있는 방법 가짓수를 구하는 문제이기 때문이다.

0번째 계단에 도달할 수 있는 방법은 '아무것도 안 하는 것'이다. 

그러므로 '아무것도 안 한다'라는 방법을 사용하기에 1이라고 저장을 해두는 것이다.

 

정 납득이 안 간다면 그냥 이렇게 코드를 작성해도 문제는 없다

 

 

class Solution:
    def climbStairs(self, n: int) -> int:
        
        if n < 4:
            return n
        
        dp=[0]*(n+1)
        
        dp[2] = 2
        dp[3] = 3

        for i in range(4, n+1):
            dp[i] = dp[i-1]+dp[i-2]

        return dp[n]

 

결과