[BOJ] 11052 붕어빵 판매하기

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

 너무 쉬워서 자세한 설명은 생략한다.

 난이도는 그냥 1/5

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF (987654321)
 
using namespace std;
 
int n;
int cost[1005];
int cache[1005][1005];
 
int dp(int b, int c)
{
    if(b==0) return 0;
    if(c>n) return -INF;
 
    int &ret=cache[b][c];
    if(ret!=-1) return ret;
 
    int ma=0;
    for(int i=c;i<=b;i++)
        ma=max(ma,dp(b-i,i)+cost[i]);
 
    return ret=ma;
}
 
int main()
{
    memset(cache,-1,sizeof(cache));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&cost[i]);
    printf("%d",dp(n,1));
    return 0;
}