3장 다이나믹 프로그래밍 - (3) 문제 풀이 5 [2156번 - 포도주 시식]

#include <iostream>

using namespace std;

int d[10001];

int a[10001];

int main(void) {

// d[n]은 n개의 잔이 있을 때, 가장 많이 마시는 양

int n;

cin >> n;

for (int i = 1; i <= n; i++) {

cin >> a[i];

}

d[1] = a[1];

d[2] = a[1] + a[2];

for (int i = 3; i <= n; i++) {

d[i] = d[i - 1]; // 마지막 잔을 안마신 경우

if (d[i] < a[i] + a[i - 1] + d[i - 3]) // 마지막 잔을 2연속으로 먹은 경우

d[i] = a[i] + a[i - 1] + d[i - 3];

if (d[i] < a[i] + d[i - 2]) // 마지막 잔을 1연속으로 먹은 경우

d[i] = a[i] + d[i - 2];

}

cout << d[n] << endl;

return 0;

}