C++ 11052 카드 구매하기[DP]

 

 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
	std::vector<int> Cards;
	std::vector<int> DP;

	int N;

	std::cin >> N;

	Cards.resize(N+1);
	DP.resize(N+1);

	for (int i = 1; i <= N; i++)
	{
		std::cin >> Cards[i];
	}

	for (int i = 1; i < Cards.size(); i++)
	{
		for (int j = 1; j <= i; j++)
		{
			DP[i] = std::max(DP[i], DP[i - j] + Cards[j]);
		}
	}
	// 카드 1개 -> N
	// 카드 2개 -> N, (N-1)+1
	// 점화식 다시 봐보기

	std::cout << DP[N];
	return 0;
}