백준[2156] - 포도주 시식

문제

백준 2156 문제 보기

접근 방법

경우를 총 3가지로 나누어 dp로 해결한다. n번째 포도주를 마시지 않을 때와 마실 때(첫번째 잔인지, 연속된 잔인지 구분).
n번째 잔을 마시지 않을 경우, n-1번째 잔은 마셧는지 안마셧는지 여부에 상관없이 최대값을 저장.
n번째 잔이 연속된 첫 잔일 경우, 이전 잔은 무조건 마시지 않었어야 한다.
n번째 잔이 연속된 잔일 경우, 이전 잔은 연속된 첫잔이여야 한다.
if(n번째 잔을 마시지 않을 때) dp[i][0] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]);
if(n번째 잔이 첫 시작 잔) dp[i][1] = dp[i - 1][0] + a[i];
if(n번째 잔이 연속된 잔) dp[i][2] = dp[i - 1][1] + a[i];

코드

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
int a[10001];
int dp[10001][3];

int main() {

    cin >> n;

    memset(dp, 0, sizeof(dp));
    memset(a, 0, sizeof(a));

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

    dp[1][1] = a[1];

    for(int i = 2; i <= n; i ++) {

        int temp = max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][0] = max(temp, dp[i - 1][2]);

        dp[i][1] = dp[i - 1][0] + a[i];

        dp[i][2] = dp[i - 1][1] + a[i];
    }

    int t = max(dp[n][0], dp[n][1]);
    int ans = max(t, dp[n][2]);

    cout << ans;
    return 0;
}