[백준] 2156번 포도주

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int arr[10010], d[10010]; //d[i]: i번째까지 시식했을 때 최대 포도주 양

int main(){
    fastio;
    int n; cin>>n;
    for(int i=1; i<=n; i++) cin>>arr[i];
    
    d[1]= arr[1]; d[2]=arr[1]+arr[2];
    for(int i=3; i<=n; i++){
        d[i] = max({d[i-3]+arr[i-1] + arr[i], d[i-2]+arr[i], d[i-1]});
    }
    cout<<d[n];
}

[참고]

https://codingnotes.tistory.com/157

[풀이]

d[i-3] + arr[i-1] + arr[i]: i-1, i번 연속 두 잔 마시기

그 전에(i-2)는 마시면 안 되니까 → d[i-3]

패턴: O X O O

 

d[i-2] + arr[i]: i번만 마시고 i-1은 건너뜀

패턴: O X O

 

d[i-1]: i번 포도주는 마시지 않음

즉, 지금까지 마신 것 그대로 유지

-> i번째 포도주를 마시거나 말거나, 가장 이득이 되는 경우를 선택