[백준 2156] 포도주 시식, C++

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 본 문제는 1 ~ n까지의 포도주 잔에 들어있는 포도주 양이 각각 다를 때, 가장 많은 양의 포도주를 마시는 방법을 구하는 문제다. 이때, 연속으로 3잔을 마실 수 없다. 예를 들어 3개의 포도주 잔이 있을 때, 3번째 잔을 마시는 방법과 안마시는 방법은 oox, oxo, xoo가 있다. 이 3가지 방법중 가장 많이 마시는 수를 계산하면 된다. 즉, d[n] = max(d[n-1], d[n-2]+a[n], d[n-3] + a[n] + a[n-1])를 구하면 된다. 이때, d[1] = a[1], d[2] = a[1] + a[2]로 초기화를 하고 3~n까지 진행해야 한다.

#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int d[10001];
int a[10001];
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    d[1] = a[1];
    d[2] = a[1]+a[2];
    for (int i = 3; i <= n; i++)
        d[i] = max(d[i-1], max(d[i-2]+a[i], d[i-3]+a[i]+a[i-1]));
    printf("%d", d[n]);
}