LeetCode Climbing Stairs (JavaScript)

링크 : https://leetcode.com/problems/climbing-stairs/description/

문제 설명

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

---

문제 풀이

DFS를 이용하여 모든 경우의 수를 구하려고하면 시간 초과 오류가 발생

이 문제는 Combination을 이용하여 풀어야 함

즉, 1과 2를 선택한 갯수에 따른 조합 갯수를 구하면 됨.

(총 자릿수 n, 2 선택 갯수 r -> nCr을 구하면 됨)

e.g. n = 6인 경우

1이 6개, 2가 0개인 경우 -> 6C0 -> 1

1이 4개, 2가 1개인 경우 -> 5C1 -> 5

1이 2개, 2가 2개인 경우 -> 4C2 -> 6

1이 0개, 2가 3개인 경우 -> 3C3 -> 1

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const getCombination = (n, r) => {
        let result = 1;

        if (r < 0 || r > n) {
            return 0;
        }
        if (r === 0 || r === n) {
            return 1;
        }

        for (let i = 1; i <= r; i++) {
            result *= (n - i + 1);
            result /= i;
        }

        return Math.round(result);
    }

    let k = 0;
    let answer = 0;
    while (2 * k <= n) {
        const nn = n - k;

        answer += getCombination(nn, k);

        k += 1;
    }

    return answer;
};

---

결론

규칙성을 찾고 해당 규칙을 로직으로 구현하면 됨(이 문제는 조합을 구하는 규칙을 찾는게 핵심)