[dp/난이도 하] 2156번 포도주 시식

간단한 다이나믹 프로그래밍 문제이다.

예제에 나온걸 예로 들면

6 10 13 9 까지만 있다고 쳤을때

             x

         x  o

    x   o  o 

연속해서 세잔을 마실 수가 없으므로 세가지 경우가 나타날 수 있다.

1.마지막 잔을 마시지 않고 그전 잔만 있다고 생각했을때 최대 마실수 있는양

2.마지막 잔을  + 그전전 잔까지만 있다고 생각했을때 최대 마실수 있는양

3. 마지막 잔과 그 전 잔 + 그전전 까지의 포도주의 최대 시식량

이 세가지 경우중에 최대가 되는것을 택하면 6 10 13 9 의 양을 가진 포도주잔들이 있을때 마실수 있는 포도주의 최대 양을 구할 수 있게 된다.

#include<iostream>
#include<algorithm>
using namespace std;
int input[10001];
int dp[10001];
int n;
int main()
{
    cin>>n;
    
    for(int i=1; i<=n; i++)
        cin>>input[i];
    
    dp[0]=0;
    dp[1] = input[1];
    dp[2] = input[1]+input[2];
    
    for(int i=3; i<=n; i++)
    {
        dp[i] = max(dp[i-1],dp[i-2]+input[i]);
        dp[i] = max(dp[i],dp[i-3]+input[i]+input[i-1]);
    }
    
    cout<<dp[n]<<endl;
    return 0;
}