baekjun 2579. 계단 오르기

 계단을 오를 때 어디서부터 오를 것인지, 오를 때 3칸 연속 오르면 안되기에 이를 처리해주는 곳만 있다면 해결할 수 있다.

#include <iostream>
#include <algorithm>
#include <cstring>
 
#define LOWEST    -3000000
 
using namespace std;
 
int N;
int steps[301];
int cache[302][2];
 
int getMaxStep(int level, int ctn) {
    if (level == N)
        return steps[N];
    if (level > N)
        return LOWEST;
    int locCtn = ctn;
    if (locCtn < 0)
        locCtn = 0;
    int & ret = cache[level][locCtn];
    if (ret != -1)
        return ret;
    ret = 0;
    if (ctn == 1)
        return ret = getMaxStep(level + 2, 0) + steps[level];
 
    return ret = max(getMaxStep(level + 1, ctn + 1), getMaxStep(level + 2, 0)) + steps[level];
}
 
int main() {
    cin >> N;
    memset(cache, -1, sizeof(cache));
    steps[0] = 0;
    for (int i = 1; i < N + 1; i++)
        cin >> steps[i];
    cout << getMaxStep(0, -1) << endl;
    //system("pause");
    return 0;
}