문제
접근 방법
경우를 총 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; }