11052. 카드 구매하기

 

 

 

DP 로 풀어야한다. 

카드를 고를 때 N= 4라면 

3장을 살 때의 최댓값은 +1장의 카드 

2장을 살 때의 최댓값은 +2장의 카드

1장을 살 때의 최댓값은 +3장의 카드

0장을 살 때의 최대값은 +4장의 카드 

 

이므로 위 중에서 가장 높은 값을 찾아내야 했다. 

 

고로 N장을 살때엔 

N-1장을 살 때 최댓값은 +1장의 카드를 고르게 되는 점화식을 추려낼 수 있어야 한다.. 

 

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
using namespace std;

#define MAX 1001

int requireCount;
int fdp[MAX];
int dp[MAX];

void calc()
{
	for (int i = 1; i <= requireCount; i++)
	{
		
		for(int j = 1; j<= i;j++)
		{
			if (dp[i] < dp[i - j] + fdp[j])
			{
				dp[i] = dp[i - j] + fdp[j];
			}
			else
			{
				dp[i] = dp[i];
			}
		}
	}
}

int main() {

	cin >> requireCount;

	for (int i = 1; i <= requireCount; i++)
	{
		int num; 
		cin >> num; 
		fdp[i] = num; 
	}

	calc();
	
	cout << dp[requireCount];


	return 0;
}