[백준] 11052 카드 구매하기 c++

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

11052번: 카드 구매하기

 

N개의 카드를 구매할 것인데 그중에서 제일 돈을 많이 지불하는 방법을 찾으면 된다.

1,,,N개까지 의 카드가 들어있는 카드팩이 가격이 다 다르다.

dp[i]는 i개의 카드를 구매할 때의 최댓값이 담겨있는 배열이다.

5개의 카드를 구매할때 최댓값은

do[1]+dp[4], dp[2]+dp[3]  

중에 더 큰 값이다.

 

#include<iostream>
#include<algorithm>

using namespace std;

int N;
int num[10001];
int dp[10001];
int main()
{
	cin >>  N;
	for (int i = 1; i <= N; i++)
	{
		cin >> num[i];
		dp[i] = num[i];
	}

	
	for (int i = 2; i <= N; i++)
	{
		for (int j = 1; j <= i/2; j++)
		{
			dp[i] = max(dp[i], dp[j] + dp[i - j]);
		}
	}
	cout<<dp[N];


}