[LeetCode 해석 및 풀이] 70. Climbing Stairs(계단 오르기)

LeetCode 문제 해석 및 풀이 방법

문제 70. Climbing Stairs(계단 오르기)

난이도 : 쉬움🟢 바로가기

 

문제 설명

영문

You are climbing a staircase. It takes n steps to reach the top.

 

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

 

한글

당신은 계단을 오르고 있습니다. 꼭대기에 도달하려면 n단계가 필요합니다.

 

매번 1단계 또는 2단계를 오를 수 있습니다. 정상까지 올라갈 수 있는 방법은 몇 가지입니까?

 

제한조건

• 1 <= n <= 45

 

입출력 예

입력	출력
n = 2	2
n = 3	3

 

해답 및 해설

파이썬 (Python)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        
        n -= 2
        a, b = 1, 2
        while n:
            a, b = b, a+b
            n -= 1
        
        return b

 

피보나치로 풀면 되는 유명한 문제. n번째 계단을 오르는 방법은 n-1번째 계단을 오르는 방법들에서 계단 한 칸을 오르는 것과 n-2번째 계단을 오르는 방법들에서 계단 2칸을 오르는 방법이 있다. 따라서 계단을 오르는 방법의 가짓수는 다음 항이 이전 두 항을 더한 값이 되는 수열, 즉 피보나치 수열이 되게 된다.

 

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

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

 

 굳이 이렇게 풀 이유는 없지만 neetcode 로드맵에서 나온 대로 dp로 풀면 다음과 같다. 보통 재귀로 풀 때와 dp로 풀 때를 비교해주는 편