[백준] 11052번: 카드 구매하기

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

11052번: 카드 구매하기

문제가 길지만 한마리로 얘기하면, 1~N장의 카드 셋과, 각각의 가격이 주어졌을 때 N장의 카드를 구입하기 위해 지불할 수 있는 최대 가격을 구하는 문제이다.

역시나 DP를 이용해서 풀 수 있다.

 

N장의 카드의 최대 가격은 dp[N-i] + price[i](i = 1 to N)의 최대값이다.

이 점을 이용해서 잘 구현하면 됨!

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

int main() {
	int N;
	int price[1001];
	int dp[1001];

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> price[i];

	fill(dp, dp + 1001, 0);

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i] = max(dp[i], dp[i - j] + price[j]);
		}
	}

	cout << dp[N];

	return 0;
}