문제접근🤔

dp[n]은 n개의 카드를 구매하는데 지불해야 하는 금액의 최대값
p[n] n개가 들어있는 카드팩의 금액
점화식 유도

4개의 카드를 구매하는 방법
1. 3개의 카드를 구매하는데 지불해야 하는 금액의 최대값 + 1개가 들어있는 카드팩의 금액
  
  → dp[3] + p[1]
2. 2개의 카드를 구매하는데 지불해야 하는 금액의 최대값 + 2개가 들어있는 카드팩의 금액
  
  → dp[2] + p[2]
3. 1개의 카드를 구매하는데 지불해야 하는 금액의 최대값 + 3개가 들어있는 카드팩의 금액
  
  → dp[1] + p[3]
4. 4개가 들어있는 카드팩의 금액
  
  → dp[0] + p[4]
이 중에서 최대를 구하면 됨

$$ dp[n-i] + p[i] $$

//pseudo code
cin >> n;
while // n까지
	while // i까지
		dp[n-i] + p[i] 중에서 최대값

놓쳤던 부분😅

코드😁

2016 KB

0 ms

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

int n;
std::vector<int> dp;
std::vector<int> p;

void input_setting()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	int i;

	i = 0;
	std::cin >> n;
	dp.resize(n + 1, 0);
	p.resize(n + 1);
	while (++i <= n)
		std::cin >> p[i];
}

void solution()
{
	int i = 0;

	while (++i <= n)
	{
		int j = 0;
		while (++j <= i)
			dp[i] = std::max(dp[i], dp[i - j] + p[j]);
	}
	std::cout << dp[n];
}

int main(void)
{
	input_setting();
	input();
	solution();
	return (0);
}