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