문제링크 : https://www.acmicpc.net/problem/11052
#include<bits/stdc++.h>
using namespace std;
#define mine
vector<int> p(1001);
int dp[1001];
int main(){
int n;
cin >> n;
for(int i=1; i<=n; i++){
cin >> p[i];
}
for(int i=1; i<=n; i++){
// dp[1] 부터 순서대로 값을 계산하게 된다.
// dp[i-j] + p[j] 의 최대값이 곧 dp[i]의 값이 된다.
for(int j=1; j<=i; j++){
dp[i] = max(dp[i], dp[i-j]+p[j]);
}
}
cout << dp[n];
return 0;
}
내가 해결하지 못하여 다른사람의 블로그를 참고하였다. 하지만 핵심은 하나다. 이 문제에서 N개의 카드가 주어지는데, 이러한 카드가 주어질 때 이 카드들 만으로 계산을 순차적으로 하면 된다. 이러한 테크닉을 배우게 되었다.
dp[i] = max(dp[i], dp[i-j]+p[j]) 이러한 방법을 잊지말자.