2156 포도주 시식

백준 2156 포도주 시식 https://www.acmicpc.net/problem/2156

다음과 같은 규칙이 적용된다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

2579 계단오르기와 유사해 보이는 문제이지만 포도주 잔을 선택할때에 대한 조건은 없다.

즉, 시작점과 끝점 모두 불분명하다는 것이다.

연속적으로 3잔을 모두 마실 수 없는것을 이용해서 

현재를 기준으로 0잔 마셨을 때 , 1잔 마셨을 때, 2잔 마셨을 때로 점화식을 세워보면

DP[N][M] : N까지 현재 M잔 마셨을 때 마신 최대 포도주 양

1. M = 0

현재 0잔 마셨으므로 N-1기준으로 0잔,1잔,2잔 마신 최댓값을 구하면 된다.

DP[N][0] = max(DP[N-1][0], DP[N-1][1], DP[N-1][2])

2. M = 1

현재 1잔 마셨으므로 N-1기준으로는 0잔 마신 경우밖에 없다.

 DP[N][1] = DP[N-1][0] + Wine[N]

3. M = 2
현재 2잔 마셨으므로 N-1기준으로는 1잔 마신 경우밖에 없다.

DP[N][2] = DP[N-1][1] + Wine[N]

#include <cstdio> #include <algorithm> using namespace std; int main(){     int N, arr[10001] = { 0 };     int D[10001][3] = { 0 };     scanf("%d", &N);     for (int n = 0; n < N; n++)         scanf("%d", &arr[n]);     D[1][2] = D[1][1] = arr[0];     for (int n = 2; n <= N; n++){         D[n][0] = max(max(D[n - 1][0], D[n - 1][1]), D[n - 1][2]);         D[n][1] = D[n - 1][0] + arr[n - 1];         D[n][2] = D[n - 1][1] + arr[n - 1];     }     printf("%d\n", max(max(D[N][0], D[N][1]), D[N][2]));     return 0; } Colored by Color Scripter

cs