[2156] 포도주 시식

내 풀이 : 2차원 DP

dp[i][j]는 마지막으로 마신 잔이 j번째 잔일 때, j번째 잔을 포함한 연속으로 마신 잔의 횟수가 i일 때 총 마신 양

코드

#include <cstdio>
#include <algorithm>
using namespace std;
long long v[10001];
long long dp[3][10001];
int n;


/*
dp[i][j] : 마지막까지 연속되게 먹은 수가 i이게 총 j잔을 먹을 때 최대 먹은 양
*/

int main(void) {
	scanf("%d", &n);
	for (int j = 1; j <= n; j++) {
		scanf("%lld", &v[j]);
	}
	dp[0][1] = 0;
	dp[1][1] = v[1];
	dp[2][1] = -1;
	long long a, b, c;
	for (int i = 2; i <= n; i++) {
		a = dp[0][i - 1];
		b = dp[1][i - 1];
		c = dp[2][i - 1];
		dp[0][i] = max(a, (max(b, c)));
		dp[1][i] = dp[0][i - 1] + v[i];
		dp[2][i] = dp[1][i - 1] + v[i];
	}
	a = dp[0][n];
	b = dp[1][n];
	c = dp[2][n];
	printf("%lld\n", max(a, max(b, c)));
	return 0;
}

백준님 풀이 : 1차원 DP

dp[i] : i번째 와인까지 시식했을 때 최대 먹은 양

1. i번째부터 봤을 때 최근에 0개를 연속해서 먹은 경우 ???X
2. i번째부터 봤을 때 최근에 1개를 연속해서 먹은 경우 ??XO
3. i번째부터 봤을 때 최근에 2개를 연속해서 먹은 경우 ?XOO

a = dp[i-1]; b = dp[i-2] + v[i]; c = dp[i-3] + v[i-1] + v[i];

dp[i] = max(a,max(b,c))

코드

#include <cstdio>
#include <algorithm>
using namespace std;
long long v[10001];
long long dp[10001];
int n;

int main(void) {
	scanf("%d", &n);
	for (int j = 1; j <= n; j++) {
		scanf("%lld", &v[j]);
	}
	long long a, b, c;
	dp[1] = v[1];
	dp[2] = dp[1] + v[2];
	a = dp[2];
	b = dp[1] + v[3];
	c = v[2] + v[3];
	dp[3] = max(a, max(b, c));
	
	for (int i = 4; i <= n; i++) {
		a = dp[i - 1];
		b = dp[i - 2] + v[i];
		c = dp[i - 3] + v[i - 1] + v[i];
		dp[i] = max(a, max(b, c));
	}

	printf("%lld\n", dp[n]);
	return 0;
}