[성실코딩 12일차] 백준 #11052 카드 구매하기 / DP

예제 입력이 아래와 같을 때, 문제풀이 

10 

1 1 2 3 5 8 13 21 34 55 

구현 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n; // 카드 개수
int arr[1001];
vector<vector<int>> DP;

void populateDP() {

	// 첫번째 행 - 카드 1개 들어있는 카드팩
	for (int j = 1; j <= n; j++) {
		DP[1][j] = arr[1] * j;
	}

	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (j<i) {
				DP[i][j] = DP[i-1][j];
			}
			else if (j==i) {
				DP[i][j] = max(DP[i-1][j],arr[j]);
			}
			else {
				int new_one = DP[i][i] + DP[i][j-i];
				DP[i][j] = max(new_one,DP[i-1][j]);
			}
		}
	}

	populateDP();

	cout << DP[n][n] << endl;

	return 0;
}