[BOJ-11052]붕어빵판매하기

음 일단...... 

* k 개 남았을 때 최적의 값을 구해간다. 

k ~ [0,n-1] 

남은 수량 : total

판매할 개수 : sell

total 개중 sell 개를 판매한다. 그리고 이전에 total - sell 의 양인 total 중 [1,total-sell] 개를 판매한 것 중 최적 에서 가장 큰 값을 끌어온다. 

이 최대 값을 현재 dp[total][sell] 에 합산하여 값을 저장한다.

시간이 말도 안되게 오래 나온 걸로 봐서 "맞았습니다" 는 받았는데 방정식을 제대로 세우진 못한 것 같다라는 생각이 든다;

다른 사람들은 0ms 나왔는데 464ms 나오는 건 내가 문제가 있는 거네;;;;;;

#include<cstdio>
#include<cstring>
// 4
// 1 5 6 7
// f(total, sold#)
// if(total < sold#) nothing
// 1 5 6 7 f(4,1) f(4,2) f(4,3) f(4,4)
// 0 0 0 0 f(3,1) f(3,2) f(3,3) /f(3,4)
// 0 0 0 0 f(2,1) f(2,2) /f(2,3) /f(2,4)
// 0 0 0 0 f(1,1) /f(1,2) /f(1,3) /f(1,4)
int max2(int a, int b){
    return (a>b)?a:b;
}
 
int sold[1001];
int dp[1001][1001];
 
int dy(int total, int sell){
    if(total < sell || total <= 0) return 0;
    int &ret = dp[total][sell];
    if(ret != -1) return ret;
    ret = sold[sell];
    int temp = 0;
    for(int i = 1 ; i <= total-sell ; i++){
        temp = max2(temp, dy(total-sell, i));
    }
    ret += temp;
    return ret ;
}
 
int main(){
    int n; scanf("%d" , &n);
    int result = 0 ;
    for(int i = 1 ; i <= n ; i++) scanf("%d", &sold[i]);
    memset(dp, -1, sizeof(dp));
    for(int to = 1 ; to <= n ; to++){
        for(int se = 1 ; se <= n ; se++){
            result = max2(result, dy(to, se));
        }
    }
    printf("%d",result);
    return 0;
}