[2156] 포도주 시식

알고리즘 실력이 너무 바닥인 거 같다..
오랜만에 복습 겸 초급 문제를 풀고 있는데 아직까지 제자리인 기분..ㅠㅠ
알고리즘은 기계적인 외움보다 원리를 계속 고민해야하는 데 이 과정이 되게 어렵다...

이 문제는 전형적으로 연속성을 따지는 문제 이다.

2차원 배열

나는 2차원 배열로 풀었다.
dp[i][j] => i번째까지 마시는 포도주에서 j번 연속으로 마셨을 때 최대양을 담았다.

1. dp[i][0] -> 0번 연속 해서 마신다. i번째를 선택하지 않았다는 뜻이다. 따라서 그 전번째인 i-1번째 중 최대값을 저장한다.
2. dp[i][1] -> 1번 연속해서 마신다. i번째를 선택하고 i-1번째를 선택하지 않았다는 뜻이다. 따라서 dp[i-1][0] + a[i] 와 같다.
3. dp[i][2] -> 2번 연속해서 마신다. i,i-1번째를 선택하고 i-2를 선택하지 않았다는 뜻이다. 따라서 dp[i-1][1] + a[i] 와 같다.

코드는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<set>
#include<cstdlib>
#include<sstream>
using namespace std;
long long  dp[10001][3];
int a[10001];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, k;
	cin >> n;
	long long  maxx = -1;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		
	}
	dp[1][0] = 0;
	dp[1][2] = 0;
	dp[1][1] = a[1];
	for (int i = 2; i <= n; i++) {
		dp[i][0] = max(max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]);
		dp[i][1] = dp[i - 1][0] + a[i];
		dp[i][2] = dp[i - 1][1]+ a[i];
	}

	for (int i = 0; i <= 2; i++) {
		maxx = max(dp[n][i], maxx);
		//cout << dp[n][i] <<' ';
	}
	cout << maxx;
	return 0;
}

1차원 배열

1차원 배열로 풀 수도 있다.
dp[i] 를 i번째 까지 마셨을 때, 포도주의 최대 양이라고 지정한다.

1. 0번 연속 (= i번째 마시지 않음) d[i-1] 와 같다.
2. 1번 연속 (i번째 마시고 i-1 번째 마시지 않음) dp[i-2]+ a[i]
3. 2번 연속 (i,i-1번째 마시고, i-2번째 마시지 않음 ) dp[i-3]+ a[i]+a[i-1]

이 중 최대 값을 구하면 된다.