백준) 2156 포도주 시식

포도주 시식

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

포도주를 최대한 마시려고 한다. 앞에서 부터 잔들을 마실 수 있지만, 연속해서 세잔은 마실 수 없다.

계단 문제(http://js1jj2sk3.tistory.com/85?category=725178)와 같은 상황이다.

다만 한 번에 한 층만 오를 수 있게 조건만 변화했을 뿐이다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int n;
int arr[10000];
int dp[10000][3];
 
int func(int p, int cnt) {
    if (p >= n)
        return 0;
 
    int& ref = dp[p][cnt];
    if (ref != -1)
        return ref;
 
    if (cnt == 0) {
        int a = func(p + 1, 1) + arr[p];
        int b = func(p + 1, 0);
 
        return ref = max(a, b);
    }
    else if (cnt == 1) {
        int a = func(p + 1, 2) + arr[p];
        int b = func(p + 1, 0);
 
        return ref = max(a, b);
    }
    else
        return ref = func(p + 1, 0);
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", func(0, 0));
 
    return 0;
}