분석

어제 계속하다가 머리 터질거같아서 오늘 다시 하니까 이해가 되었음..

3잔 연속 마실 수 없으니까 모양이 아래와 같이 될것임.

cache[n]을 n잔을 마시기 전의 최대합이라 생각

밑의 사진과 코드를 보면서 이해를 하도록 하자..

int& ret = cache[n];
if (ret != 0) return ret;


ret = DP(n - 1);
ret = max(ret, DP(n - 2) + arr[n]);
ret = max(ret, DP(n - 3) + arr[n] + arr[n - 1]);

설명을 잘 못한다는 것은 본인이 완벽히 이해를 못했기 때문이기도 한듯...

그래서 아래 블로그의 글과 코드와 위에 사진이랑 같이 보면 이해가 어느정도는 나는 됬었음.

https://omyodevelop.tistory.com/52

CPP코드

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

#define MAX 10001
#define endl "\n"

int cache[MAX];
int arr[MAX];

int DP(int n)
{
	// 기저
	if (n <= 2) return cache[n];

	// 캐시
	int& ret = cache[n];
	if (ret != 0) return ret;

	// 구함
	ret = DP(n - 1);
	ret = max(ret, DP(n - 2) + arr[n]);
	ret = max(ret, DP(n - 3) + arr[n] + arr[n - 1]);
	
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
	
	int n;
	cin >> n;
	
	for (int i = 1; i < n + 1; ++i)
		cin >> arr[i];
	
	// Init
	cache[1] = arr[1];
	cache[2] = arr[1] + arr[2];
	
	cout << DP(n) << endl;

	return 0;
}

그런데 문제가 위에 코드로 백준에다가 내면은 시간초과 뜸.

그래서 제출할 때는 아래 코드로 제출을 하면 될듯

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

#define MAX 10001
#define endl "\n"

int cache[MAX];
int arr[MAX];

int main()
{
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
	
	int n;
	cin >> n;
	
	for (int i = 1; i < n + 1; ++i)
		cin >> arr[i];
	
	// Init
	cache[1] = arr[1];
	cache[2] = arr[1] + arr[2];
	
	for (int i = 3; i < n + 1; ++i)
	{
		int& ret = cache[i];
		ret = cache[i - 1];
		ret = max(ret, cache[i - 2] + arr[i]);
		ret = max(ret, cache[i - 3] + arr[i] + arr[i - 1]);
	}

	cout << cache[n] << endl;

	return 0;
}