11052번

11052번 - 붕어빵 판매하기

D[N] = N개 일때 붕어빵 판매로 얻을 수 있는 최대 이익.

완전 탐색을 통해 푼 뒤 캐시를 이용해 시간을 줄여주면 된다.

붕어빵을 A개 팔았다면

D[N] = D[N-A] 가 되는데 A의 범위가 1~N까지 이므로 그 중에서 최대값을 구하면 된다.

따라서 D[N] = max(D[N],D[N-A]) 가 된다.

<정답 코드 >

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int N;
int P[1001];
int ans;
int D[1001];
int go(int n)
{
 
    if (n == 0)
    {
        return 0; 
    }
 
    if (D[n] != 0)
    {
        return D[n];
    }
 
    for (int i = 1; i <= n; i++)
    {
        D[n] = max(D[n],go(n - i) + P[i]);
    }
 
    return D[n];
}
int main()
{
    cin >> N;
    memset(D, 0, sizeof(D));
 
    for (int i = 1; i <= N; i++)
    {
        cin >> P[i];
    }
 
    cout << go(N) << endl;
    
 
    return 0;
}

<완전 탐색 - 시간 초과>

#include<iostream>
#include<algorithm>
using namespace std;
int N;
int P[1001];
int ans;
void go(int n, int sum)
{
    if (n < 0)
    {
        return;
    }
 
    if (n == 0)
    {
        ans = max(ans, sum);
        return; 
    }
 
    for (int i = 1; i <= N; i++)
    {
        go(n - i, sum + P[i]);
    }
 
}
int main()
{
    cin >> N;
 
    for (int i = 1; i <= N; i++)
    {
        cin >> P[i];
    }
 
    go(N,0);
 
    cout << ans << endl;
    
 
    return 0;
}