백준[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;
}