[210508][백준/BOJ] 11052번 카드 구매하기

문제

입출력

풀이

민규가 N개의 카드를 사려고 한다.
1부터 N까지 카드가 존재하고 p는 각 카드의 값이다. 이를 통해 카드를 구매하는데 필요한 최대값을 구하는 문제이다.

4개의 카드가 있을때 이를 구매하는 최대값은
카드4
카드3+카드1
카드2+카드2
카드1+카드3

총 4가지 경우 중에 존재한다.
이를 코드로 구현하면 다음과 같다.

D[4] = D[4]
D[4] = D[3] + A[1]
D[4] = D[2] + A[2]
D[4] = D[1] + A[3]

점화식은 다음과 같다.

  for (int i = 2; i <= n; ++i)
      for (int j = 1; j <= i; ++j)
          d[i] = max(d[i], d[i - j] + A[j]);

코드

#include <bits/stdc++.h>
using namespace std;

int d[100002];
int A[100002];

int dp(int n)
{
	d[1] = A[1];
	for (int i = 2; i <= n; ++i)
		for (int j = 1; j <= i; ++j)
			d[i] = max(d[i], d[i - j] + A[j]);
	return d[n];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> A[i];

	cout << dp(n);
}