백준 11052 카드구매하기 c++ //dp 관찰방법

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

11052번: 카드 구매하기

1.dp 관찰방법

i행에 주머니(동전)을 한개씩 !추가! 하면서 target(N개 카드) 를 채워나간다.

 

2.의사코드

1. i행에 1번째 주머니, 2번째 주머니를 추가해나가면서 관찰한다.

2. 관찰결과 위쪽(이번에 추가된 주머니 미사용하는경우) 과

d[j-i] + arr[i]( j-i개 카드를 추가하기 위해 이번에 추가된 주머니 사용하는경우)를 비교해야함을 알아낸다.

 

3.전체코드

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

int n,a[1004],dp[1004][1004];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}

	//dp[i][j] : i번째 주머니 !!추가!!시, j개카드를 만드는데 드는 최대비용

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (j - i >= 0) {
				dp[i][j] = max(dp[i - 1][j], dp[i][j-i]+a[i]);
			}
			else
				dp[i][j] = dp[i - 1][j];
				
		}
	}
	
	/*for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= n; ++j) {
			cout << dp[i][j]<<" ";
		}
		cout << "\n";
	}*/

	cout << dp[n][n];

	return 0;
}