문제
풀이
•
그냥 완전 탐색에 메모이제이션 추가된 느낌
•
n 개의 카드팩을 사는데 최대로 드는 비용을 dp에 저장
•
실제로 모든 경우를 다 사보는데 만약에 이미 사본경우가 있으면 저장해둔 값 쓴다.
•
이떄 n 이 음수가 되면 안되기떄문에 if (num - i >= 0) 조건문을 걸어준다.
•
아니면 if (num < 0) return (-999999) 이런식도 가능하다.
구현
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int n;
vector<int> cards;
vector<int> dp;
void pre() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
void input() {
cin >> n;
cards.resize(n + 1);
dp.resize(n + 1);
for(int i = 1; i <= n; i++)
cin >> cards[i];
}
int rec(int num) {
int price;
price = 0;
if (num == 0)
return (0);
if (dp[num])
return (dp[num]);
for(int i = 1; i <= n; i++)
if (num - i >= 0)
price = max(rec(num - i) + cards[i], price);
dp[num] = price;
return (dp[num]);
}
void solve() {
cout << rec(n) << endl;
}
int main() {
input();
solve();
return (0);
}
C++
복사
