70. Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

 

문제 이해

계단을 오르는데 한 번에 1칸, 2칸 오를 수 있다. N 층을 올라갈 때 구할 수 있는 모든 경우의 수를 출력하는 문제.

 

접근

1 층 [1]

2 층 [1,1] [2]

3 층 [1,1,1] [1,2] [2,1]

4 층 [1,1,1,1] [1,1,2] [1,2,1] [2,1,1] [2,1,2]

 

현재 층의 경우의 수는 ARR[N] = ARR [N-2] + ARR [N-1]

이전 층의 합으로 유도가 가능하다.

 

 

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

 

회고

단순 DP 문제였다. 다른 사람 풀이를 보니 심플하게 풀었네 피보나치 응용문제인데 이런 -0- 암기 코더는 이래서 문제야

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

 

위 코드에서 resize를 사용했는데 어제 사용한 reserve 랑 차이가 갑자기 궁금해졌다.

https://m.blog.naver.com/PostView.nhn?blogId=yalleeya&logNo=110112424512&proxyReferer=https%3A%2F%2Fwww.google.com%2F

vector reserve와 resize의 차이

resize는 메모리 공간을 할당 후 그 크기만큼 사용할 수 있게 만든다.

reserve는 메모리 공간을 할당할 뿐 컨테이너를 추가한 것이 아니라 사용할 수 없다.

 

아래는 최 선생님에 간단한 설명

 

B 풀이

dp 는 계속 값을 더해준다는 개념을 사용하여 최소의 element 로 사용함

class Solution {
public:
    int climbStairs(int n) {
        if (n == 0) return 1;
        vector<int> arr(3, 0);
        arr[0] = arr[1] = 1;
        for (int i = 2; i <= n; ++i) {
            arr[i % 3] = arr[(i - 1) % 3] + arr[(i - 2) % 3];
        }
        return arr[n % 3];
    }
};

 

O 풀이

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

 

Z 풀이

class Solution {
public:
    int climbStairs(int n)
    {
        if( n == 1 )
            return 1;
        else if( n == 2 )
            return 2;
        
        // 피보나치 수열과 동일하게 증가
        int n1 = 1;
        int n2 = 2;
        int nCur = 0;
        for( int i = 2 ; i < n ; i++ )
        {
            nCur = n1 + n2; //  n = (n-1) + (n-2)
            n1 = n2;        
            n2 = nCur;
        }

        return nCur;
    }
};