카드 구매하기 C++ - 백준 11053

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

이 문제의 경우 합이 N이 되는 모든 경우를 살펴봐야 하기 때문에
일단 O(N^2) 알고리즘의 경우 시간이 얼마나 걸리는지 확인해보았다.
(시간 제한 1초)
최악의 경우 100만번이므로 O(N^2)도 사용해도 되었다.
그래서 아래와 같이 구상했다.

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

int N;
int dp[1001];
int inn;
int cost[1001];

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	
	cin >> N;
	for(int i=1;i<=N;i++){
		cin >> cost[i];
	}
	for(int i=1;i<=N;i++){
		dp[i]=dp[0]+cost[i];
		for(int j=1;j<=i;j++){
			dp[i]=max(dp[i-j]+cost[j],dp[i]);
		}
	}
	cout << dp[N];
}

합이 i가 되는 경우 중 돈을 최대로 사용하는 경우를 채택해 dp테이블에 저장하는 방식으로 알고리즘을 구상했다.