11052번. 카드 구매하기

점화식

d[n]
= v[n] vs dp[1] + v[n - 1] + dp[2] + v[n - 2]....

점화식 만들어 나가는 과정

• 입력 예제 1번으로 진행함.
  

코드

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

int main()
{
	// d[n] : 카드 n개를 구매하기 위해 지불해야 하는 금액의 최대값은? 
	// 카드 arr[0] ~ arr[n-1]을 이용함.

	// d[1] : 카드 1개를 구매하기 위해 지불해야 하는 금액 
	// d[1] = arr[1]
	// 1

	// d[2] : 카드 2개를 구매하기 위해 지불해야 하는 최대 금액은? 
	// d[1] + arr[1] vs arr[2] 
	// 2 vs 5 -> 5

	// 인덱스 순은 0부터가 아니라 1부터
	// d[3] : 카드 3개를 구매하기 위해 지불해야 하는 최대 금액은? 
	// d[2] + arr[1] vs arr[3] vs d[1] + arr[2]
	// 5 + 1 vs 7 vs 1 + 5 -> 7

	// d[4] : 카드 4개를 구매하기 위해 지불해야 하는 최대 금액은? 
	// d[3] + arr[1] vs arr[4] vs d[2] + arr[2] vs d[1] + arr[3]
	// 7 + 1 vs 7 vs 5 + 5 vs 1 + 7 
	// 8 vs 7 vs 10 vs 8
	 
	int n;
	cin >> n;

	vector<int >v(n + 2, 0);
	for (int i = 1; i <= n; ++i)
		cin >> v[i];
	
	vector<int>dp(n + 2, 0);
	dp[1] = v[1];

	for (int i = 2; i <= n; ++i)
	{
		int max = v[i];
		for (int j = 1; j <= i - 1; ++j)
		{
			int val = dp[j] + v[i - j];
			if (max < val)
				max = val;
		}
		dp[i] = max;
	}

	//for (auto iter : dp)
	//	cout << iter << endl;
	cout << dp[n];
}