2156. 포도주 시식

1. 해결방법

• Dynamic Programming
• DP[n] : n번째까지 마신 포도주 최대 양을 의미
• DP[1] = juice[1] = 0
• DP[2] = juice[1] + juice[2]
• DP[3] = ??? 
• DP[3] 은 juice[1] + juice[3]  OR  juice[2] + juice[3]  OR  DP[2]
• DP[n] = ???
• DP[n] 은 DP[n-1]  OR  DP[n - 2] + juice[n]  OR  DP[n - 3] + juice[n - 1] + juice[n] 

2. Solution

// Dynamic Programming
#include <iostream>
#include <algorithm>

#define MAX 10000 + 1
#define endl "\n"

using namespace std;

int n, answer = -1;
int juice[MAX];
int DP[MAX];

void Initial()
{
    DP[0] = juice[0] = 0;
    DP[1] = juice[1];
    DP[2] = juice[1] + juice[2];
}

void Input()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> juice[i];
    }
}

void Solution()
{   
    for(int i = 3; i <= n; i++)
    {
        DP[i] = max(DP[i - 3] + juice[i - 1] + juice[i], max(DP[i - 2] + juice[i], DP[i - 1]));
    }
    cout << DP[n] << endl;
}

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Initial();
    Solution();
}

 

3. 알아야 할 개념

• 포도주의 index 를 1부터 시작하고자 한다면, #define MAX 값은 주어진 최대값 + 1을 해야 한다.

// 포도주 양의 범위 1~10000

// 경우1) index 0 부터 시작
#define MAX 10000

// 경우2) index 1 부터 시작
#define MAX 10000 + 1