[baekjoon 1500]최대 곱

dp로 푼사람이 아무도 없어서 올려본다.

점화식을 세우면 다음과 같다

dp[s][k] = max(dp[s-X][k-1] * X) (1 <= X <= S-1)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int S, K;
	scanf("%d %d", &S, &K);
	vector<vector<long long>> dp(S + 1, vector<long long>(K + 1));
	for (int i = 1; i <= S; i++)
	{
		dp[i][1] = i;
	}

	for (int k = 2; k <= K; k++)
	{
		for (int s = 1; s <= S; s++)
		{
			for (int x = 1; x <= s - 1; x++)
			{
				dp[s][k] = max(dp[s][k], dp[s - x][k - 1] * x);
			}
		}
	}

	printf("%lld\n", dp[S][K]);
}