C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 11052번:붕어빵 판매하기 답

//D[i] = 붕어빵 i개를 팔았을 때 얻을 수 있는 최대 수익

//P[i] = 붕어빵 세트를 팔았을 때 얻을 수 있는 수익

//마지막 j를 팔 때 최대 수익을 남길 수 있다면 j를 제외한 나머지 붕어빵 개수는 i-j개

//D[i-j]에 나머지 P[j]를 더하면 D[i]가 된다.

//모든 경우의 수를 살펴봐 가장 큰 값이 최대 수익이 된다.

// D[i] = max(D[i],P[j]+D[i-j])

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int N,big = 0;
    cin >> N;//남은 붕어빵
    int *D = new int[N + 1];
    int *P = new int[N + 1];
    for (int i = 1; i <= N; i++)
    {
        cin >> P[i];
    }
    D[0] = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= i; j++)
            D[i] = max(D[i],P[j] + D[i - j]);
    cout << D[N];
}