[LEETCODE] 70: Climbing Stairs(Python)

Climbing Stairs - LeetCode

문제 설명

계단을 오를 때에는 계단 한 칸을 오르는 방법, 계단 두 칸을 오르는 방법 2가지가 존재한다. n번째 계단까지 도달하는 방법의 개수를 구해보자.

나의 풀이

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

1번째 계단까지 올라가는 방법은 1개, 2번째 계단까지 올라가는 방법은 2개이다. 그 이후 n개의 계단을 오르는 방법은 현재-1번째 계단에서 한 칸을 올라가는 경우와 현재-2번째 계단에서 두 칸을 올라가는 경우와 동일하기 때문에 간단한 DP 테이블을 작성하거나 변수 2개를 활용해서 문제를 해결할 수 있다.

처음에는 a, b 변수를 사용해서 O(n) 메모리 없이 사용해보려고 했는데, dp 테이블을 작성하는 방식보다 시간이 더 나와서 위의 코드처럼 작성했다. 또 1, 2를 예외처리하는 경우 시간이 엄청 줄어들었다…

시간복잡도

dp테이블을 작성하는 for문에서 O(n)이 걸린다.