5. Climbing Stairs

문제 설명

n개의 계단을 1개 또는 2개의 스텝으로만 오를 수 있다. 이때, n개의 계단을 오를 수 있는 경우의 수를 구하는 문제이다. 

처음에는 combination을 활용해 접근하였다. (n-n/2)C(n/2)의 식에 n을 대입하는 방식으로 답을 구하려 했지만 조합의 값을 구하기 위해서는 팩토리얼을 사용해야만 한다. 즉, n의 값이 20만 넘어가도 수가 어마어마하게 커진다. long long unsigned int를 활용해도 이 수를 담아내지 못한다. 

class Solution {
public:
    long long int fact(int n) {
        if (n == 0 || n == 1)
            return 1;
        else
            return n * fact(n - 1);
    }
    int comb(int n, int r){
        return fact(n) / (fact(r) * fact(n-r));
    }
    int climbStairs(int n) {
        int sum = 0;
        for(int i = 0; i <= n/2; i++){
            sum += comb(n-i, i);
        }
        return sum;
    }
};

두 번째 방식으로는 Dynamic Programming을 활용했다. 계단을 한 개 또는 두 개씩 밖에 오르지 못한다는 특성을 보았을 때, n번째 계단은 n-1번째 계단에서 한 개 오르기, n-2번째 계단에서 두 개의 계단 오르기로 나뉠 수가 있다. 즉 stair [n] = stair [n-2] + stait [n-1]이라는 식이 나오게 된다. 익숙한 피보나치 수열이 보인다.

코드의 길이, 메모리, 러닝타임, 모든 것이 전의 코드보다 효율적이다.

class Solution {
public:
    int climbStairs(int n) {
        int dp[100] = {0};
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};