[Easy] 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?

 

예시

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

 

풀이 과정

첫번째 접근은 경우의 수를 크게 2가지로 나누어 생각했다. 모두 1인 경우와, 2를 추가하는 경우로 나누었다. 

하지만 내 코드는 2가 들어가는 조합을 구하는 코드였고, 이것을 순열로 만드려니 어떤 코드를 추가해야 할 지 감이 잡히지 않았다. 

그래서 2를 넣는 경우의 수로 푸는 답을 참고하려고 다른 분들 코드를 봤더니, 이 문제는 피보나치 수열로 푸는 문제라는 걸 알았다.. 

그래서 두번째 접근은 피보나치 수열로 접근해보았다.

코드만 보고는 왜 이렇게 푸는 건지 이해가 어렵다.

NeetCode의 설명 영상을 보고 코드를 보는 것이 좋다. 

 

풀이 코드

첫 시도 

var climbStairs = function(n) {
    let result = [];
    
    // 1) 모두 1
    let arr1 = [];
    for(let i = 0 ; i < n ; i++){
        arr1.push(1);
    }
    
    result.push([...arr1]);
    
    
    // 2) 2를 하나씩 추가
    let sum = 0;
    let rest = n;
    let arr2 = [];
    
    do{
        arr2.push(2);
        sum += 2;
        rest -= 2;
    }while(sum > rest + 2);
    
    if(rest !== 0){
        for(let i = 0 ; i < rest ; i++){
            arr2.push(1);
        }
        result.push(arr2);
    }
    
    
    console.log(result)
    return result.length;
};

 

두번째 시도

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    
   let two = 1, one = 1;
    
    for (let i = 0; i < n-1; i++) {
        let temp = one;
        one = one + two;
        two = temp;
    }
    
    return one;
};

 

---

참고 영상

 

https://youtu.be/Y0lT9Fck7qI