🖊️ 문제

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

---

🖊️ 풀이

dp..
열심히 막 .. 점화식을 세워봤으나
자꾸 실패했다. ....

수준 ...

슬펐다

실패작

#include <iostream>
using namespace std;

int dp[10'005][4];

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int n;
	cin >> n;

	//dp[1][0] = 0;
	//dp[1][1] = 6;
	//dp[1][2] = 6;
	//
	//dp[2][0] = 0;
	//dp[2][1] = 10;
	//dp[2][2] = 6 + 10 = dp[1][1] + 10 = 16;

	//dp[3][0] = 16;
	//dp[3][1] = 6 + 13 = dp[1][2] + 13 = 19;
	//dp[3][2] = 10 + 13 = dp[2][1] + 13 = 23;

	//dp[4][0] = 23;
	//dp[4][1] = dp[2][2] + 9 = 16 + 9 = 25;
	//dp[4][2] = dp[3][1] + 9 = 19 + 9 = 28;

	//dp[5][0] = 28;
	//dp[5][1] = dp[3][2] + 8 = 23 + 8 = 31;
	//dp[5][2] = dp[4][1] + 8 = 25 + 8 = 33;

	//dp[6][0] = 33;
	//dp[6][1] = dp[4][2] + 1 = 28 + 1 = 29;
	//dp[6][2] = dp[5][1] + 1 = 31 + 1 = 32;

	int n1, n2;
	cin >> n1;
	cin >> n2;

	dp[1][1] = n1;
	dp[1][2] = n1;

	dp[2][1] = n2;
	dp[2][2] = n1 + n2;

	int cur;
	for (int i = 3; i <= n; i++) {
		cin >> cur;
		dp[i][1] = dp[i - 2][2] + cur;
		dp[i][2] = dp[i - 1][1] + cur;
		dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]);
		dp[i][3] = max(dp[i][1], max(dp[i][2], dp[i][0]));
	}

	cout << dp[n][3] << endl;
}

점화식 자체를 잘못 세웠다.
나는..
i번째 수에 대해 최댓값들을 4개나 저장했다.
1. dp[i][0] : i-1번째 수까지의 최댓값
2. dp[i][1] : i-2번째 수를 선택하고 2번 선택했을 때 + 현재 값
3. dp[i][2] : i-1번째 수도 선택하고, i번째 수도 선택헀을 때

점화식 자체가 잘못됐다.

점화식을 세울 때
현재 상황에서 어떤 걸 저장해야 다음번에 추가 계산없을 수 있는지, 최댓값을 구해야 한다면 현재 상황에서의 최댓값을 구하자.

---

일단 포도주를 연속 3개가 안되니까

... [0][1][2][3] 이렇게 4개가 있다고 했을 때
가능한 수는
1. [3] + [2] + [0]까지의 최댓값
2. [3] + [1]까지의 최댓값
3. [2]까지의 최댓값

이렇게 된다.

#include <iostream>
using namespace std;

int arr[10'005];
int dp[10'005];

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) 
		cin >> arr[i];

	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];

	for (int i = 3; i <= n; i++) {
		dp[i] = max(dp[i - 1], max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]));
	}

	cout << dp[n] << endl;
}