[백준] 2156.cpp : 포도주 시식

www.acmicpc.net/problem/2156

2156번: 포도주 시식

---

• 2579번 계단 오르기와 유사한 문제이다.
• 조건이 3잔 연속 마시지 않는다인데, 이 조건이 무조건 1잔 아니면 2잔 연속 마셔야 한다는 뜻은 아니다.
• 포도주를 마시지 않고 넘어가는 경우도 가능하기 때문에, 점화식에 비교를 하나 더 추가해주면서 DP 배열을 갱신시켜야 한다.

---

#include <iostream>

using namespace std;

int n;
int drink[10001];

int nex[10001];

int main(void)
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n;

    for(int i = 1 ; i <= n ; i++) cin >> drink[i];      // 포도주 입력

    nex[1] = drink[1];                                  // 1,2 번째는 직접 입력
    nex[2] = drink[1] + drink[2];

    for(int i = 3 ; i <= n ; i++)                       // 3 - N 까지
    {                                                   // i-2 번째 최댓값 + 이번에 마심                (X Y 0 1)
                                                        // i-3 번째 최댓값 + 직전에 마시고 이번에도 마심 (X 0 1 1)
                                                        // i-1 번째 최댓값                             (X Y Z 0)
        nex[i] = max(max(nex[i-2] + drink[i] , nex[i-3] + drink[i-1] + drink[i]), nex[i-1]);
    }

    cout << nex[n] << endl;
}

---

• 1등 소스코드 참고 : www.acmicpc.net/source/3760615
• DP 배열을 3개만 만들어서 포도주를 입력받음과 동시에 최댓값 계산하는 점화식도 구성이 가능하다.
• 0번 - 최댓값 그대로 유지 (이번에 마시지 않음)
• 1번 - 이전에 마시지 않은 0번 + 이번에 마심 (한번 쉬었다가 마심)
• 2번 - 이전에 마신 1번 + 이번에 또 마심 (두번 연속 마심)

---

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

int dp[3], tmp;

int maxi()
{
    return max(dp[0], max(dp[1], dp[2]));
}

int main()
{
    int n, x;
    scanf("%d", &n);
    while(n--)
    {
        scanf("%d", &x);
        tmp = maxi();
        if(dp[1]) dp[2] = dp[1] + x;
        dp[1] = dp[0] + x;
        dp[0] = tmp;

        printf("%d %d %d\n", dp[0], dp[1], dp[2]);
    }
    printf("%d\n", maxi());
}