3장 다이나믹 프로그래밍 - (2) 문제 풀이 5 [11052번 붕어빵 판매하기]

#include <iostream>

using namespace std;

int d[1001];

int p[1001];

int main(void) {

int n; 

cin >> n;

for (int i = 1; i <= n; i++) {

cin >> p[i];

}

for (int i = 1; i <= n; i++) {

d[i] = p[i];

int temp = i / 2;

for (int k = 1; k <= temp ;k++) {

if (d[i] < d[i - k] + d[k])

d[i] = d[i - k] + d[k];

}

}

cout << d[n] << endl;

return 0;

}