기업투자(2662).cc

#include<iostream>

using namespace std;

int main() {
	int A[21][301] = { 0 }; //A[i][j] : 기업 i가 j금액을 투자했을 때 얻는 이익
	int DP[21][301] = { 0 }; //D[i][j] : j금액을 i까지의 기업들이 투자했을 때 얻는 최대 이익
	int path[21][301] = { 0 };
	int path_money[21] = { 0 };
	int money, num;//투자 금액, 기업 갯수
	int temp;

	//입력
	cin >> money >> num;
	for (int i = 1; i <= money; i++)
	{
		cin >> temp;
		for (int j = 1; j <= num; j++)
			cin >> A[j][temp];
	}
	//다이나믹
	for (int i = 1; i <= num; i++)
	{
		for (int j = 1; j <= money; j++)
		{
			for (int k = 0; k <= j; k++)
			{
				temp = A[i][k] + DP[i - 1][j - k];
				if (DP[i][j] < temp)
				{
					DP[i][j] = temp;
					path[i][j] = k; //i기업이 투자한 금액
				}
			}
		}
	}

	//최대이익 출력
	cout << DP[num][money] << endl;

	//각 기업에 투자한 액수
	int ind = 0;
	int m = money;
	for (int i = num; i > 0; i--)
	{
		path_money[ind++] = path[i][m];
		m -= path[i][m];
	}
	for (int i = ind - 1; i >= 0; i--)
		cout << path_money[i] << " ";
	return 0;
}