[백준] 2662 기업 투자

백준 2662 기업 투자

• https://www.acmicpc.net/problem/2662

• 얻을 수 있는 최대 이익은 dp로 쉽게 구할 수 있었으나, 각 기업에 투자한 액수를 출력하는 것에 조금 헤맨 문제

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 300;
const int MAXM = 20;

int n,m;

//[company][money]
int profit[MAXM+1][MAXN+1]; 
int cache[MAXM + 1][MAXN + 1];
int bestChoice[MAXM + 1][MAXN + 1] = { 0 };

int getMaxProfit(int company, int money) {
	if (company > m || money == 0) return 0;

	int& ret = cache[company][money];
	if (ret != -1) return ret;

	//투자하지 않는 경우
	int choice = 0;
	ret = getMaxProfit(company + 1, money);

	//1만원 ~ 가지고 있는 돈만큼 투자하는 경우 
	for (int i = 1; i <= money; ++i) {
		int cand = profit[company][i] + getMaxProfit(company + 1, money - i);
		if (ret < cand) {
			ret = cand;
			choice = i;
		}
	}

	bestChoice[company][money] = choice;
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	memset(cache, -1, sizeof(cache));

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		int money;
		cin >> money;
		for (int j = 1; j <= m; ++j) 
			cin >> profit[j][i];
	}

	cout << getMaxProfit(1,n)<<"\n";

	int sumOfChoice = 0;
	for (int i = 1; i <= m; ++i) {
		int choice = bestChoice[i][n - sumOfChoice];
		cout << choice << " ";
		sumOfChoice += choice;
	}
	return 0;
}