[Leetcode] Climbing stairs

문제 링크

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

Climbing Stairs - LeetCode

 

문제 해설

• 계단의 정상에 도달하려면 n번의 걸음을 해야한다.
• 매번 1개 혹은 2개의 계단을 오를 수 있다.
• 얼마나 많은 방법으로 정상에 오를 수 있는가

 

나의 풀이 (Python3)

class Solution:
    def climbStairs(self, n):
        
        if n <= 2:
            return n
        
        dp = [0 for i in range(n+1)]
        dp[0] = 0 # 없는 값이지만 계산을 쉽게 하기 위해 0으로 초기화
        dp[1] = 1
        dp[2] = 2
        
        for i in range(3, n+1):
            dp[i] = dp[i - 1] + dp[i - 2]
        
        return dp[n]

• n = 1이면 계단이 한 개이므로 결과는 1
• n = 2이면 계단이 두 개, 결과는 step1 + step1, step2로 2
• 이후 케이스를 계속 반복하면 규칙성이 보이는데 n에서는 n - 1번째 결과 값과 n - 2번째 결과 값의 합이 된다.
  • f(n) = f(n-1) + f(n-2) 로 피보나치와 동일하다.

 

Github : https://github.com/Limseunghyun95/code_test/blob/master/leetcode/climbing_stairs.py

GitHub - Limseunghyun95/code_test: 코딩 테스트 연습 공간

 

참고 자료

• https://www.youtube.com/watch?v=Y0lT9Fck7qI&ab_channel=NeetCode