[DP]백준2156번 포도주 시식

백준2156 포도주 시식

우선 DP 배열은 현재 포도주까지 마실 수 있는 최대의 포도주 양으로 정한다.

DP에서 가장 중요하게 생각해야 하는 것은, 모든 경우의 수를 다 계산하고, DP 배열에는 그 중 최선을 저장하는 것이다.

DP는 현재 배열의 값을 선택할 때 이전 배열에서 값을 가지고 오는데, 이것은 이전 배열에 값을 집어넣을 때 최선의 값을 선택해 저장해놓았기 때문이다.

연속으로 놓여 있는 3잔의 포도주를 마실 수 없다는 조건이 있기 때문에, 각 포도주 잔에 대하여 다음과 같은 경우들이 존재한다.

1. 이번 포도주를 마시지 않는 경우

   포도주 세 잔을 연달아 마실 수 없기 때문에 지금 현재 내 포도주를 마시지 않는다면 바로 직전까지 최대로 마실 수 있는 포도주의 양을 선택하면 된다.

2. 이번 포도주를 마시고 직전 포도주를 마실 경우

   포도주 세 잔을 연달아 마실 수 없기 때문에 i-2 번째 포도주는 선택하지 않고, i-3번째까지 최대로 마실 수 있는 포도주의 양을 선택한 후 현재 포도주의 양을 더해주면 된다.

3. 이번 포도주를 마시고 직전 포도주를 마시지 않을 경우

   i-2번째까지 마실 수 있는 최대 포도주의 양을 선택한 후 현재 포도주의 양을 더해주면 된다.

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int N;
    
    cin >> N;
    int wines[10005];
    int answers[10005];
    for(int i=1;i<=N;i++){
        cin >> wines[i];
    }
    answers[1] = wines[1];
    answers[2] = wines[1] + wines[2];
    
    for(int i=3;i<=N;i++){
        int case1, case2, case3;
        // 이번 걸 안마심
        case1 = answers[i-1];
        // 이번 걸 마시고 바로 전 것도 마심
        case2 = wines[i] + wines[i-1] + answers[i-3];
        // 이번 걸 마시고 바로 전 것도 마심
        case3 = wines[i] + answers[i-2];
        answers[i] = max({case1,case2,case3});
    }
    cout << answers[N];
}