(c++)백준 11052번: 카드 구매하기

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

11052번: 카드 구매하기

※점화식※

dp[i] : i개 카드 구매 위해 민규가 지불해야 하는 금액의 최댓값

dp[1] = P[1]

dp[x] = max(P[x], (dp[x-j][j]중 최댓값)) (1≤j≤x/2)

 

#include <iostream>
#include <algorithm>
using namespace std;

int N;
long long P[1001];
long long dp[1001];

void DP() {
	dp[1] = P[1];
	for (int i = 2; i <= N; i++) {
		long long tmp = -1;
		for (int j = 1; j <= i / 2; j++) {
			tmp = max(tmp, dp[i - j] + dp[j]);
		}
		dp[i] = max(tmp, P[i]);
	}
	cout << dp[N] << endl;
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> P[i];
	}
	DP();
	return 0;
}