[백준 11052] 카드 구매하기

분류 : DP

 

요구사항

원하는 카드의 갯수가 주어질때 카드 값을 최대로 지불하는 금액 구하기

 

풀이

d[i]는 i개의 카드를 보유하고 있을때의 최대 값이다. d[i]는 i*map[1]로 초기화한다.

d[i] = max(d[i], map[i-j] +d[j])의 점화식으로 구한다

d[j]는 이미 앞에서 구했던 현재 j까지의 최대 값이 된다

 

#include <iostream>
#include <algorithm>

using namespace std;
int n;
int d[100100];
int map[1010];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &map[i]);
	for (int i = 1; i <= n; i++) d[i] = i*map[1];
	
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= i; j++) {
			d[i] = max(d[i], map[i - j] + d[j]);
			//cout << "map" << map[i] << " " << map[i - j] << " " << map[j] << endl;
			//cout << "i " << i << " " << j << endl;
		}
	}
	cout << d[n] << endl;
}