[C++] BOJ 2156번: 포도주 시식

문제 링크

문제 풀이

dp를 이용하여 해당 포도주를 마셨을 때가 연속 1번 마신 경우, 연속 2번 마신 경우, 그리고 해당 포도주를 마시지 않은 경우 3가지로 나누어 문제를 풀어냈다.

코드

#include <bits/stdc++.h>

using namespace std;

int n;
int arr[10006];

int dp1[10006]; // 1번 마셨을 때
int dp2[10006]; // 2번 마셨을 때
int dp3[10006]; // 안 마셨을 때

int result;

void calcDp(int depth)
{
    if (depth > n)
        return;
    if (depth == 1)
    {
        dp1[1] = arr[1];
        dp2[1] = 0;
        dp3[1] = 0;
    }
    else
    {
        dp1[depth] = dp3[depth - 1] + arr[depth];
        dp2[depth] = dp1[depth - 1] + arr[depth];
        dp3[depth] = max(max(dp1[depth - 1], dp2[depth - 1]), dp3[depth - 1]);
    }
    calcDp(depth + 1);
}

int main(void)
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> arr[i];

    calcDp(1);

    result = max(max(dp1[n], dp2[n]), dp3[n]);

    cout << result << '\n';

    return 0;
}