[알고리즘] c++ cpp 포도주 시식

포인트

1. 다이나믹 프로그래밍의 이해

2. //  막잔을 기준으로 3번째 앞에 잔을 마시고, 2번째 앞에 잔을 건너뛰고 1번째 앞에 잔 + 막잔
    //  막잔을 기준으로 2번째 앞에 잔을 마시고 + 막잔
    //  막잔을 마시지 않고, 1번째 앞에 잔의 최댓값

 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include<iostream>
#include<cstring>

#define MAX 10001
using namespace std;

int n;
int map[MAX];
int d[MAX];

int main() {

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> map[i];


    d[0] = map[0] = 0;
    d[1] = map[1];
    d[2] = map[1] + map[2];

    //  막잔을 기준으로 3번째 앞에 잔을 마시고, 2번째 앞에 잔을 건너뛰고 1번째 앞에 잔 + 막잔
    //  막잔을 기준으로 2번째 앞에 잔을 마시고 + 막잔
    //  막잔을 마시지 않고, 1번째 앞에 잔의 최댓값
    for (int i = 3; i <= n; i++) d[i] = max(d[i - 3] + map[i - 1] + map[i], max(d[i - 2] + map[i], d[i - 1]));

    cout << d[n] << endl;
    return 0;
}