[Easy] Leetcode | 70. Climbing Stairs | Dynamic programming

 

 

- 문제
계단을 오르는 데 정상까지 오르려면 n번의 step을 거쳐야 한다.
한 번에 오를 수 있는 계단의 수는 1 또는 2 step이다. 정상까지 오를 수 있는 방법의 수는? 

Note: n은 양의 정수로 주어진다.

- 풀이
n을 1부터 조금씩 나열해보면 규칙이 보인다.

n=1) 1
n=2) 2
n=3) 3
n=4) 5
n=5) 8
n=6) 13
...

피보나치 수열이다.

즉, 위의 각 결과가 f의 함수의 결과라고 했을 때 각 결과는 다음과 같다.

n=1) 1
n=2) 2
n=3) f(2) + f(1)
n=4) f(3) + f(2)
n=5) f(4) + f(3)
n=6) f(5) + f(4)
...

재귀 함수로 구현하면 시간 복잡도는 지수 시간의 복잡도를 가진다. O(2^n) 이 경우 시간 초과로 테스트를 통과하지 못한다.
위에서 f(5)를 예로 들어보면 f(5)는 다음과 같이 중복되는 값을 여러번 가진다.
 
f(5) = f(4) + f(3)
f(5) = f(4) + (f3) + f(2) + f(1)
f(5) = f(3) + f(2) + f(2) + f(1)
f(5) = f(2) + f(1) + f(2) + f(2) + f(1)

중복되는 계산을 막기 위해 동적 계획법의 memoization 기법을 통해 중복되는 값을 저장해두고 재사용하는 방식을 사용한다.
f(5)일 경우 f(1)~f(4)의 값이 필요하고 f(n)은 f(1)~f(n-1) 범위의 값이 필요하다. 따라서 vector에 n-1개 만큼의 공간을 만들어 각 요소에 f(i)의 값을 저장한다. 만약 n이 1, 2, 3일 경우는 값을 그대로 반환하여 빠르게 함수를 종료한다. 그렇지 않을 경우 이전에 저장된 값을 통해 결과를 반환한다.

class Solution 
{
public:
    int climbStairs(int n)
    {
        if (n <= 3)
        {
            return n;
        }

        std::vector<int> v;
        int size = n - 1;
        v.reserve(size);

        v.push_back(1);
        v.push_back(2);
        v.push_back(3);

        // v[0]: 1
        // v[1]: 2 
        // v[2]: 3 
        // v[3]: v[2] + v[1]
        // ...
        // v[n]: v[n-1] + v[n-2]
        
        for (int i = 3; i != size; ++i)
        {
            v.push_back(v[i - 1] + v[i - 2]);
        }
        
        return v[n - 2] + v[n - 3];
    }
};