[LeetCode/Python] 70. Climbing Stairs

99클럽 코테 스터디 | 비기너 | 6일차

---

https://leetcode.com/problems/climbing-stairs/description/

 

접근 방법 1

Queue를 사용해서 문제 해결 시도 -> Time Limit Exceeded Error

from collections import deque

class Solution:
    def climbStairs(self, n: int) -> int:
        queue = deque([0])
        ways = 0

        while queue:
            current_step = queue.popleft()
            if current_step == n:
                ways += 1
            elif current_step < n:
                queue.append(current_step + 1)
                queue.append(current_step + 2)
                
        return ways

 

접근 방법 2

동적 프로그래밍 (DP) 개념 활용

from collections import deque

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            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]