[백준]Baekjoon11052(Dynamic Programming)

풀이

이 문제는 주어진 붕어빵들에 대해 세트를 어떻게 구성해야 최대의 이득을 낼 수 있는지에 관한것이다.

풀이는 생각보다 직관적이다.

n개를 선택했을 때 가장 이득이 큰 값을 memo배열에 넣게되는데

예를들어 3개를 선택했을 때 이득이 가장 큰 경우는

memo[2] + num[1] , memo[1] + num[2], memo[0] + num[3] 중 가장 최댓값일 것이다.

(여기서 num은 처음에 주어진 단순한 세트의 가격이다.)

이런식으로 처음부터 memo를 구해가면서 답을 도출해내는 것이다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int main()
{
	int memo[1001];
	memset(memo, 0, sizeof(int) * 1001);
	int num[1001]; num[0] = 0;
	int N; int n;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> n;
		num[i] = n;
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			memo[i] = max(memo[i], memo[i - j] + num[j]);
		}
	}
	cout << memo[N] << '\n';
}