baekjun 2156. 포도주 시식

 두칸 뛰는 문제

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
int grapes[10000];
int cache[10002];
int N;
 
int getMaxGrape(int pos) {
    if (pos == N + 1)
        return 0;
    int & ret = cache[pos + 1];
    if (ret != -1)
        return ret;
    ret = 0;
    for (int i = pos + 1; i < N; i++) {
        int twoSum = 0;
        for (int j = 0; j < 2; j++) {
            if (i + j < N) {
                twoSum += grapes[i + j];
                ret = max(ret, getMaxGrape(i + j + 1) + twoSum);
            }
        }
    }
    return ret;
}
 
int main() {
    int i = 0;
    memset(cache, -1, sizeof(cache));
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> grapes[i];
    cout << getMaxGrape(-1) << endl;
    //system("pause");
    return 0;
}