백준 알고리즘 기초 강좌
3장 다이나믹 프로그래밍 - (3) 문제 풀이 5 [2156번 - 포도주 시식]
살구르
2017. 8. 17. 18:14
#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;
}