[2156] 포도주 시식

이문제는 계단오르기 문제와 동일하게 생각했다가 아닌걸 깨닳았다.

계단과 달리 이문제는 두칸을 뛰어넘을 수 도 있다.

#include <cstdio>
#include <algorithm>
using namespace std;
​
int main()
{
    int N = 0;
    int d[10001];
    int a[10001];
    scanf("%d", &N);
​
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &a[i]);
    }
​
    d[0] = 0;
    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-1]+a[i]));
    }
    int res = 0;
    for(int i = 1;i<=N;i++){
        if(d[i] > res){
            res = d[i];
        }
    }
    printf("%d\n", res);
}

우선 경우를 3가지로 나눴다.

1. 이 와인을 안마실경우 — d[i] = d[i-1]

2. 전 와인을 안마시고 현재와인을 마셧을 경우 — d[i] = d[i-2]+a[i]

3. 전 와인을 마시고 현 와인을 마셨을 경우 — d[i] = d[i-3]+a[i-1]+a[i]

3번의 경우가 가장 생각하기 어려웠다.

첫번째 두번째 같은경우 i-3을 해버리면 -값이 나오므로 와인 숫자로 초기화를 해두었다.

마지막을 꼭 밟아야하는 계단오르기와 달리 중간에 최댓값이 있을 수 있으므로 반복문 안에서 최댓값을 찾았다.