(c++)백준 2156번: 포도주 시식

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

앞에서 포도주를 마셨는지 안마셨는지가 뒤에 포도주를 마실 수 있는지에 영향을 주므로, 해당 순서 포도주를 마셨을 때의 최대 포도주의 양과 마시지 않았을 때의 양을 따로 계산해 주었다.(2차원 배열)

 

※점화식※

dp[i][0] : (앞에서부터) i번째 포도주를 마시지 않기로 했을 때 지금까지 마신 포도주의 최대 양

dp[i][1] : (앞에서부터) i번째 포도주를 마시기로 했을 때 지금까지 마신 포도주의 최대 양

 

dp[x][0] = max(dp[i-1][1], dp[i-2][1]) (1칸 이전에 포도주를 마셨을 때, 2칸 이전에 포도주를 마시고 1칸 이전에는 안 마셨을 때)

dp[x][1] = max(dp[i-1][0] + Wine[i], dp[i-2][0] + Wine[i-1] + Wine[i]) (1칸 이전에 포도주를 안마시고 이번 칸에서 마실 때, 2칸 이전에 포도주를 안 마시고 1칸 이전과 이번 칸에서 마실 때) 

 

☆3번 연달아 마실 수 없으므로 x-2번째 값까지 신경써야 한다.

 

#include <iostream>
#include <algorithm>//max
using namespace std;

int n;
//dp[i][0] : i번째 포도주 마시지 않았을 때 지금까지 최대로 마실 수 있는 포도주의 양
//dp[i][1] : i번째 포도주 마셨을 때 지금까지 최대로 마실 수 있는 포도주의 양
long long dp[10001][2];
int Wine[10001];

void DP() {
	dp[1][0] = 0;
	dp[1][1] = Wine[1];
	dp[2][0] = dp[1][1];
	dp[2][1] = dp[1][1] + Wine[2];

	for (int i = 3; i <= n; i++) {
		dp[i][1] = max(dp[i - 1][0] + Wine[i], dp[i - 2][0] + Wine[i-1] + Wine[i]);
		dp[i][0] = max(dp[i - 1][1], dp[i - 2][1]);
	}
	if (dp[n][0] > dp[n][1])
		cout << dp[n][0] << endl;
	else
		cout << dp[n][1] << endl;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> Wine[i];
	}
	DP();
	return 0;
}