[leetCode/JS] 70. Climbing Stairs

난이도 [ 😊 ] Easy

 

문제 설명

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칸 씩 올라 갈 때, 모든 경우의 수는 얼마인가?

 

입출력 예

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

 

---

 

 

내 솔루션

• 예전 피보나찌 알고리즘의 DP(Dynamic Programming)이 쓰인다.
• DP의 기본인 큰 작업을 하기 위해 작은 작업부터 계산한다.를 적용하면 된다.
• 만약 n = 1 일때, 1개 [1]
• n = 2 일 때, 2개 [1, 1], [2]
• n = 3 일 때, 3개 [1, 1, 1], [1, 2], [2, 1]
• n = 4 일 때, 5개 [1, 1, 1, 1], [1, 1, 2], [2, 1, 1], [1, 2, 1], [2, 2]
• n = 5 일 때는 [n-1] + [n-2] 인 8이 된다.
• 결론적으로 계단 5개가 있을 때, 계단, 4개 일때와 3개 일때의 경우의 수를 더하면 5개의 경우의 수가 나온다.
• 점화식으로 보면 f(n) = f(n-1) + f(n-2) 가 된다.

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

 

감상평

• 피보나찌 알고리즘을 못 풀어봤거나 DP를 모르면 개고생한다.
• 알면 Easy! 모르면 쒯.

 

 

var climbStairs = function(n) {
    let two = 0, one = 1;
    for (let i = 0; i < n; i++) {
      [two, one] = [one, two + one];
    }
    return one;
};

• 재미있는 코드를 찾았다. 너무 잘했네 똑똑이야.