[맞음] 백준 2156 포도주시식 // dp

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

* 풀이

1. 완전탐색으로 시도 i번째 포도주를 먹는다 안먹는다.

문제 : 연속3번은 안된다는것을 어떻게 검사하지?

비트? -> n=10000개 의비트 -> 불가능

cnt변수? (연속으로 선택한 포도주 갯수) -> 트리에서 O로 갈때 1씩 증가시키기!

상태 : (idx, cnt) 

값 : 그 상태일때, 최대값

* 전체코드

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

ll n;
ll dp[10004][4];
ll arr[10004];

//인덱스, 연속선택카운트
ll dfs(int idx, int cnt) {
    
    if(cnt>=3) {
        return -987654321; //배제
    }

    if(idx==n) {
        return 0;
    }

    ll & ret = dp[idx][cnt];
    if(ret!=-1) return ret;
    
    //선택
    ret=max(ret,dfs(idx+1,cnt+1)+arr[idx]);

    //안선택
    ret=max(ret,dfs(idx+1,0));

    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    memset(dp,-1,sizeof(dp));
    
    cin>>n;
    for(int i=0;i<n;++i) {
        cin>>arr[i];
    }
    cout<<dfs(0,0);
    
    return 0;
}