[C++] 백준(BAEKJOON) 2579

 
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int n;
    int stair[301];
    int cache[301];
     
    int dp (int x){
        if(x==0)
            return 0;
            
        if(x==1)
            return stair[0];
        
        if(x==2)
            return stair[0]+stair[1];
            
        if(x==3)
            return max(stair[0]+stair[2],stair[1]+stair[2]);
        
        if(cache[x] != 0) 
            return cache[x];
        
        return cache[x] = max(dp(x-2), dp(x-3)+stair[x-2]) + stair[x-1];
    }
     
    int main() {
        cin >> n;
        
        for (int i = 0; i < n; i++) {
            cin >> stair[i];
        }
        
        cout << dp(n);
     
        return 0;
    }