Problem

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

Idea

현재 포도주를 선택할 수 있는 경우와 선택하지 않는 경우(중요)가 있을 수 있다
d[n] = max(d[n-3] + d[n-1] + arr[n],
d[n-2] + arr[n],
d[n-1] // 선택하지 않는경우
)

2차원 배열로 접근가능하다

d[n][k]: n 번째 포도주 차례에서 k번째로 시식하는 경우의 최대 합
k = 0: 아무것도 먹지 않은 경우
k = 1: 첫번째 시식한 경우
k = 2: 두번째 시식한 경우

d[n][1] = d[n-1][0] + arr[n]
d[n][2] = d[n-1][1] + arr[n]

d[n][0] = ??
d[n-1][2] 라고 생각 할 수 있으나, 현재 안마실 때의 최대 합은
max(d[n-1][0], d[n-1][1], d[n-1][2]) 이다

memo[1][0] = 0;
memo[1][1] = arr[1];
memo[1][2] = 0;

int ans = arr[1];
for (int i = 2; i <= N; i++) {
        memo[i][1] = memo[i-1][0] + arr[i];
        memo[i][2] = memo[i-1][1] + arr[i];
        memo[i][0] = Math.max(Math.max(memo[i-1][1], memo[i-1][2]), memo[i-1][0]) ;
        
        ans = Math.max(memo[i][0], memo[i][1]);
        ans = Math.max(ans,  memo[i][2]);
}

System.out.println(ans);