[BOJ] 2662 : 기업투자 (C++)

📖 백준 2662번 : https://www.acmicpc.net/problem/2662

조건

시간 제한	메모리 제한
1 초	128 MB

문제

어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 않은 경우는 당연히 얻게 되는 이익도 없다. 예를 들어서, 한 투자가가 4만원을 갖고 두 개의 기업들에 각각 만원 단위로 투자했을 경우 얻을 수 있는 이익은 다음과 같다.

투자 액수 (만원)	기업 A	기업 B
1	5	1
2	6	5
3	7	9
4	8	15

위의 경우 만일, 기업 A에 1만원, 기업 B에 3만원을 투자하는 경우 투자가가 얻는 이익은 14만원(5만원+9만원)이다. 4만원을 투자해서 가장 많은 이익을 얻을 경우 기업 B에만 4만원을 투자하는 경우로서 이때의 이익은 15만원이다. 여기서 투자가는 한 기업에 돈을 나누어 투자할 수는 없다.

투자액이 정해져 있고, 기업의 개수와 각 기업에 투자했을 경우에 얻게 되는 이익이 주어졌을 때 가장 많은 이익을 얻을 수 있는 투자방식과 이때의 이익금을 구하는 프로그램을 작성하라.

입력

첫째 줄에 투자 금액 N과 투자 가능한 기업들의 개수 M이 주어진다. (1 ≤ N ≤ 300, 1 ≤ M ≤ 20)

둘째 줄부터 N개의 줄에 투자액수와 각 기업이 투자가에게 주는 이익이 주어진다. 투자 금액은 항상 1보다 크거나 같고, N보다 작거나 같고, 같은 투자 금액이 두 번 이상 주어지는 경우는 없다. 즉, i번 줄에 주어지는 투자 금액은 i-1만원이다.

출력

첫 줄에 얻을 수 있는 최대 이익을 출력하고, 둘째 줄에는 각 기업에 투자한 액수를 출력한다. 최대 이익은 2^31보다 작다.

---

풀이

 입력 크기가 작고 cost와 value가 존재하면서 최대 이익금을 구하는 문제라 배낭 문제가 먼저 떠올랐다. 일반적인 배낭문제와의 차이점은 점화식의 규칙에 알맞게 반복문을 구성해야 한다는 점이다. n,m이 작기 때문에 3중반복문으로 구성해도 시간 내에 풀어낼 수 있음을 알고 접근해야 점화식을 빨리 떠올릴 수 있을 것 같다.

 dp[i][j] 에서 i는 회사, j는 투자 금액으로 생각했다. i번째 회사까지 고려했을 때, j만큼의 투자금으로 얻을 수 있는 최대 이익금을 dp[i][j]가 담고 있는 형태이다.

dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + val[i][1], dp[i-1][j-2] + val[i][2], dp[i-1][j-3] + val[i][3] .... )

dp를 i, j까지 고려했을 때의 최대 이익금을 갖도록 갱신하기 때문에, 현재 i, j에서 고려해야하는 부분은
1. 바로 이전 회사(i-1) 까지 봤을 때 j의 투자금으로 얻는 최대 이익금
2. 바로 이전 회사(i-1) 까지 봤을 때 j-1의 투자금으로 얻는 최대 이익금 + 현재 회사 i에서 1의 투자금으로 얻는 이익금
3. 바로 이전 회사(i-1) 까지 봤을 때 j-2의 투자금으로 얻는 최대 이익금 + 현재 회사 i에서 2의 투자금으로 얻는 이익금
4. ...
.
.
.
j. 바로 이전 회사(i-1) 까지 봤을 때 j-j의 투자금으로 얻는 최대 이익금 + 현재 회사 i에서 j의 투자금으로 얻는 이익금

들의 최대값으로 구성할 수 있다.

 각 기업에 투자한 액수를 출력하기 위해서 2차원 배열에 pair<int, int> vector를 둬서 현재 dp[i][j]에 해당하는 {기업, 금액}을 갖도록 만들었다. dp값이 갱신될 때, 이전 dp에 해당하는 {기업, 금액}이 동일하게 유지되게끔 만들고 필요한 경우에는 값을 추가해줬다.

코드

#include <iostream>
#include <vector>

using namespace std;

int val[21][301]; // 회사, 투자 금액
int dp[21][301];
vector<pair<int,int>> company[21][301];
int ans[21];

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int n, m;
	int tmp, a;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		for (int j = 1; j <= m; j++) {
			cin >> a;
			val[j][tmp] = a;
		}
	}

	for (int i = 1; i <= n; i++) {
		dp[1][i] = val[1][i];
		company[1][i].push_back({ 1,i });
	}

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (dp[i][j] < dp[i - 1][j]) {
				dp[i][j] = dp[i - 1][j];
				company[i][j] = company[i - 1][j];
			}
			for (int k = 1; k <= j; k++) {
				if (dp[i][j] < dp[i - 1][j - k] + val[i][k]) {
					dp[i][j] = dp[i - 1][j - k] + val[i][k];
					company[i][j] = company[i - 1][j - k];
					company[i][j].push_back({ i,k });
				}
			}
		}
	}
	for (auto& it : company[m][n]) {
		ans[it.first] = it.second;
	}
	cout << dp[m][n] << '\n';
	for (int i = 1; i <= m; i++) {
		cout << ans[i] << ' ';
	}
	

	return 0;
}