[BOJ] 11052번: 붕어빵 판매하기

11052번: 붕어빵 판매하기

풀이

D[i] = i개를 판매해서 얻을 수 있는 최대 이익
D[i] = D[i - k] + P[k] 중 최대값을 구하면 되는 간단한 문제다. i개 남은 거에서 k개를 선택한다면 i - k개 중 최대 이익 + k개 이익(P[k])를 더해주면 i개의 최대 이익이 되기 때문에 저런 관계식이 나오게 된다.

코드

#include <cstdio>
#include <cstring>
int gN, P[1001], D[1001];

inline int Max(int a, int b)
{
    return (a > b ? a : b);
}

int f(int n)
{
    if (D[n] != -1)
        return D[n];
    if (n == 0)
        return 0;
    for (int i = 1; i <= gN; ++i)
    {
        if (n - i >= 0)
            D[n] = Max(D[n], f(n - i) + P[i]);
    }
    return D[n];
}

int main()
{
    scanf("%d", &gN);
    for (int i = 1; i <= gN; ++i)
        scanf("%d", &P[i]);
    memset(D, -1, sizeof(D));
    D[1] = P[1];
    // D[n] = D[n - i] + p[i];
    printf("%d\n", f(gN));
    return 0;
}