TIL # 118 : [Algorithm] 70. Climbing Stairs

셀레스틴 허·2021년 4월 20일
0

ALGORITHM

목록 보기
17/18
post-thumbnail

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?

예시

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints

  • 1 <= n <= 45

파보나치 수열


파보나치의 수열을 생각하고 계단값을 10이라고 가정할 때 -> 우리는 8까지의 값 그리고 9까지의 값을 구한 다음 더해야 한다. 즉 n[i] = n[i-1] + n[i-2]으로 적을 수 있다!

파이썬 풀이 코드 - 32 ms/ 14.3 MB

class Solution:
    
    def climbStairs(self, n: int) -> int:
        """
        :type n: int
        :rtype: int
        """
        if n <= 2 and n >= 0:
            return n

        arr = [1,2]

        for i in range(2, n):
            arr.append(arr[i-1] + arr[i-2])
        
        return arr[n-1]

자 이제 그럼 해당 풀이를 자바스크립트로..

파이썬 풀이 코드 - 16 ms / 13.2 MB

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 2 and n >= 0:
            return n

        f = 1
        s = 2 
        c = 0 
        
        for _ in range(2, n):
            c = f + s
            f, s  = s, c
            
        return c 

자바스크립트 풀이 코드 - 80 ms / 38.4 MB

var climbStairs = function(n) {
    if(n >= 0 && n < 3) {
        return n
    }
    
    let arr = [1,2]
    for(let i=2; i < n; i++){
        arr[i] = arr[i-1]+arr[i-2]
    }
    return arr[n-1]
}

자바스크립트 진짜 묘하다..!

profile
Software Developer / 고통은 필연, 괴로움은 선택

0개의 댓글