11052

11052.cpp

#include <iostream>
#include <algorithm>

/*

이 문제는 n개의 붕어빵을 팔아서 얻을 수 있는 최대 수익을 구하는 문제이다.
붕어빵을 팔 때는 (1, 2, 3... n)개를 묶어서 팔 경우 세트	메뉴 가격을 따로 받는다.

P[i] = 붕어빵 i 개를 한 번에 팔 때 얻는 수익
D[n] = 붕어빵 n 개를 팔아서 얻을 수 있는 최대 수익

가능한 경우를 계산해 보자.
붕어빵 1개를 P[1]에 파는 경우 -> 남은 붕어빵 갯수: n-1 -> P[1] + D[n-1]
붕어빵 2개를 P[2]에 파는 경우 -> 남은 붕어빵 갯수: n-2 -> P[2] + D[n-2]
...
붕어빵 n-1개를 P[n-1]에 파는 경우 -> 남은 붕어빵 갯수: 1 -> P[n-1] + D[1]
붕어빵 n개를 P[n]에 파는 경우 -> 남은 붕어빵 갯수: 0 -> P[n] + D[0]

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

따라서 D[1]부터 D[n]까지 구해나가면 됨.
D[n]을 구하기 위해서 필요한 반복문의 갯수: 
	1. 1부터 n까지 도는 반복문
	2. 붕어빵을 파는 갯수를 늘려나가는 반복문
따라서 수행시간은 O(n^2)이 된다.

*/


int main()
{
	int n, t, temp;
	int p[1001] = { 0, };
	int d[1001] = { 0, };
	scanf("%d", &t);
	for (int i = 1; i < t + 1; i++)
	{
		scanf("%d", &temp);
		p[i] = temp;
	}

	for (int i = 1; i < t + 1; i++)
	{
		for (int j = 1; j < i + 1; j++)
		{
			d[i] = std::max(d[i], p[j] + d[i - j]);
		}
	}

	printf("%d", d[t]);
}