[Algorithm] 해커랭크 - Recursion: Davis' Staircase

https://www.hackerrank.com/challenges/ctci-recursive-staircase/problem

N개의 계단이 주어졌을 때 1, 2, 3번의 걸음으로 가는 모든 경우의 수를 구하는 문제다.

처음에는 DFS를 이용하는 줄만 알고 재귀호출을 이용한 DFS를 구현해서 풀었으나 타임아웃이 나와 2시간이나 헤메었다. 도저히 생각이 안나 해당 문제의 Discussions 게시판을 참고했고, 알고보니 이 문제는 아래의 피보나치 수 구하는 문제와 매우 비슷한 문제였다.

나는 피보나치 수열이 점화식으로 표현이 된다는 점은 알고 있었지만 점화식에 대한 응용법과 정확한 개념을 알지 못했었다. 그래서 이 문제를 풀면서 이 문제가 점화식을 활용한 DP 풀이로 해결할 수 있을 거라고 생각하지 못했다.

Discussions 게시판을 참고해 얻은 점화식이 뜻하는 바가 이해가 되지않아 아래 영상을 참고해 보았다.

https://www.youtube.com/watch?v=827t3uOU_dc

동영상을 보고 이해하니 이 문제에서 점화식을 활용해 나오는 수열은 계단이 n 개일때 올라오는 '경우의 수'의 수열과 같았다. 

메모이제이션을 활용한 점화식 풀이를 적용해 보니 모든 케이스를 통과할 수 있었다. 메모이제이션과 관련된 내용은 아래 글 참조.

http://makedotworld.tistory.com/8?category=658503 (피보나치 수 구하기 문제)

경우의 수를 구하는 함수 코드는 아래와 같다.

#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
 
map<int, int> results;
 
int dp(int stairs)
{
    if(stairs == 0)
    {
        return 1;
    }
    else if(stairs < 0)
    {
        return 0;
    }
    if(results.find(stairs) != results.end())
    {
        return results[stairs];
    }
    return results[stairs] = dp(stairs-1) + dp(stairs-2) + dp(stairs-3);
}

풀이시간 : 2~3시간

풀이 중 문제점 :

 단순한 DFS 방식으로 접근해서 타임아웃 발생, DP 관련 지식이 없어 공부함