Climbing Stairs (leetcode 70)

문제

문제 링크

solution1

51ms (92.82%)

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

n=1부터 결과값을 하나씩 쓰다보면 1,2,3,5,8,13…. 등 피보나치 수열 패턴이 나온다.
이 패턴을 알고나면 코드는 간단하게 작성이 가능하다.
역시 심플한게 속도도 빠르다.

solution2

54ms (86.39%)

var climbStairs = function (n) {
    let result = 0;
    for (i = Math.round(n / 2); i <= n; i++) {
        result += factorial(i, n - i) / factorial(n - i, n - i);
    }
    return result;
};

function factorial(num, n) {
    if (num === 0 || n < 1) {
        return 1;
    } else {
        return num * factorial(num - 1, n - 1);
    }
}

n에 숫자 하나를 대입하고 계단수별로 경우의 수를 계산하는 패턴을 찾았다.
팩토리얼이 사용됐고 패턴대로 하면 결과 값은 잘 출력된다.
하지만 복잡해서 패턴을 작성하는데 오래걸리고 가독성도 상당히 나쁘다.