문제접근
•
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]
이 중에서 최대를 구하면 됨
//pseudo code
cin >> n;
while // n까지
while // i까지
dp[n-i] + p[i] 중에서 최대값
C++
복사
놓쳤던 부분
코드
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);
}
C++
복사
