[코딩 테스트] 리트코드70 - Climbing Stairs (Easy) in Python

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개 계단씩 오를 수 있다면, 얼마나 다양한 방법으로 목적지에 갈 수 있을까?

 

 

예시

Input: n = 2

Output: 2

Explanation: There are two ways to climb to the top.

1. 1 step + 1 step

2. 2 steps

 

Constraints

• 1 <= n <=45

 

풀이

이 문제는 피보나치와 같다고 볼 수 있다!

 

재귀를 이용해 풀 수도 있겠지만, 이는 time limit에 걸린다.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        return self.climbStairs(n-1) + self.climbStairs(n-2)

시간 복잡도 = O(2^n) = O(2^45) = 무려 35조 이상!! >>>>>>>> 파이썬 1초 평균 연산 1억

 

따라서 Memoization을 이용한 재귀나,

순환문을 통해 풀어야 한다.

 

1) Memoization 이용 재귀

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

 

 

2) 순환문 이용!!

class Solution:
	def climbStairs(self, n:int) -> int:
    	if n <=2:
        	return n
        a, b = 1, 2
        for _ in range(3, n+1):
        	tmp = a + b
            a = b
            b = tmp
        return b