[백준 2662] 기업투자

문제 링크 => 2662번: 기업투자 (acmicpc.net)

2662번: 기업투자

---

다이나믹 프로그래밍 문제이다.

 

투자액이 정해져 있고, 기업의 개수와 각 기업에 투자했을 경우에 얻게 되는 이익이 주어졌을 때 가장 많은 이익을 얻을 수 있는 투자방식과 이때의 이익금을 구해야 한다.

 

이때, 이차원 배열 arr, memo, invest, visited 에 대해서 설명하자면 다음과 같다.

 

arr[x][y] => 기업 y에 금액 x 만원을 투자하는 경우 얻게 되는 이익

memo[x][y] => 기업 y에 금액 x 만원을 투자하는 경우 얻게되는 최대 이익 (memoziation)

invest[x][y] => 기업 y에 금액 x 만원을 투자할 때 얼마나 금액을 투자했는지에 대한 정보

visited[x][y] => 재귀함수를 돌리면서 방문된 (x, y) 에 대해서 memo[x][y] 를 return 하도록 함

 

문제에서 금액 총 n 만원을 입력받고 기업의 갯수 m 를 통해 다음과 같이 재귀 함수를 실행할 수 있다.

 

일단 재귀 함수 dp의 파라메터 설명을 하자면?

dp(int money, int cnt) => money : 투자할 수 있는 최대값 ,  cnt : 기업이 1 => 2 => 3 => ... => m 접근하도록 하기 위한 용도

 

dp 함수에서 얻어낼 수 있는 최댓값 result를 반환하도록 하기 위해서 0 ~ money 만원 만큼 투자하는 것을 재귀적으로 받아와서 합한 tmp 값이 result 보다 큰 경우 result를 최신화 해주고 memo, invest 값 또한 변경해준다.

 

이때 0 만원은 해당 cnt 번째 기업에 투자하지 않는 경우를 의미하고,tmp = arr[i][cnt] + dp(money - i, cnt + 1)    <= 기업 cnt 번째에 금액 i 만원을 투자하고 그걸 재귀적으로 구해서 얻어진 최종 값을 의미한다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define MOD 1000000009

using namespace std;

int n, m;
long long arr[301][21];
long long memo[301][21];
long long invest[301][21];
bool visited[301][21];

long long dp(int money, int cnt) {
	if (cnt > m) return 0;
	if (visited[money][cnt]) return memo[money][cnt];
	visited[money][cnt] = true;

	long long result = 0;
	for (int i = 0; i <= money; i++) {
		long long tmp = arr[i][cnt] + dp(money - i, cnt + 1);
		if (tmp > result) {
			result = tmp;
			memo[money][cnt] = tmp;
			invest[money][cnt] = i;
		}
	}
	return result;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int c;
		cin >> c;
		for (int j = 1; j <= m; j++) {
			cin >> arr[c][j];
		}
	}

	cout << dp(n, 1) << endl;

	for (int i = 1; i <= m; i++) {
		cout << invest[n][i] << " ";
		n -= invest[n][i];
	}

	return 0;
}