LeetCode : 70. Climbing Stairs

문제

당신은 계단을 오르고 있다. 계단의 개수는 총 $n$개이다.
계단은 한 번에 한 계단씩, 또는 두 계단씩 오를 수 있다. 계단의 꼭대기까지 오를 수 있는 방법은 총 몇 가지인가?

제약 조건

$1 \le n \le 45$

풀이

피보나치 수열 문제.

• $n$ 계단을 오를 수 있는 방법을 $f(n)$라고 정의
• 시작점에서 한 계단을 올라가는 방법과 두 계단을 올라가는 방법으로 나눌 수 있다

$f(n) = f(n-1) + f(n-2)$

이 식을 그대로 재귀로 구현한 다음에 memoization을 적용하면 끝이다.

1. 기저 사례 처리

먼저 재귀 함수의 기저 사례를 처리한다.

if (n <= 1) return 1;

2. 재귀 함수 구현

class Solution {
public:
	int climbStairs(int n) {
		// base case
		if (n <= 1) return 1;
		return climbStairs(n-1) + climbStairs(n-2);
};

$n$의 최댓값이 45로 명시되어있었기 때문에 재귀함수로도 풀리지 않을까 하여 그대로 실행시켜봤는데, 정확히 43부터 Time Limit이 발생하면서 Fail.

Stack overflow가 아닌 것을 보니 문제에서 정한 시간을 초과하는 듯하다.
Memoization이 없다면, 재귀트리의 모든 노드에 대하여 계산을 해야하기 때문에 Time complexity는 $O(2^n)$.

3. Memoization 적용

• 넉넉하게 사이즈 100짜리 int array를 선언해서 0으로 초기화
• 이미 계산한 $f(n)$에 대해서는 다시 계산하지 않도록 cache에 저장

class Solution {
public:
    int cache[100] = {0, };
    int climbStairs(int n) {
        // base case
        if(n <= 1) return 1;
        int& ret = cache[n];

        if(ret != 0) return ret;
        else{
            ret = climbStairs(n-1) + climbStairs(n-2);
            cache[n] = ret;
        }
        return ret;
    }
};

이렇게 구현하면 각 $n$값에 대해서 한 번만 계산하면 되므로 Time complexity는 $O(n)$.