백준 2662번, 기업투자 풀이

문제

백준 2662번

풀이

전형적인 DP 문제입니다.

$ dp[i][cost] = "$ $ i $번째 회사까지 $ cost $원을 사용했을 때 최대 이익금" 이라고 점화식을 세웁니다.

 

회사 하나를 늘릴 때마다 어떤 cost ($ 1 \leq cost \leq N $)를 고정시키고, prev ($ 1 \leq prev \leq cost $) 를 순회해주며 DP Table을 채워줍시다.

 

역추적은 $ dp[i][cost] $가 최댓값을 가질 때의 $ prev $의 값을 저장해두면서 $ dp[i - 1][prev] $... 이런식으로 역추적해나가면 됩니다.

 

시간 복잡도는 $ O(N^3) $이 됩니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int cost[301][301], dp[301][301], trace[301][301];

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

	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		for (int j = 1; j <= m; j++) cin >> cost[j][i];
	}

	int ans = 0, mx = 0;
	for (int i = 1; i <= m; i++) {
		for (int c = 1; c <= n; c++) {
			for (int prev = 0; prev <= c; prev++) {
				int _new = cost[i][c - prev] + dp[i - 1][prev];
				if (_new > dp[i][c]) {
					dp[i][c] = _new;
					trace[i][c] = prev;
				}
			}
			ans = max(ans, dp[i][c]);
			if (dp[i][c] == ans) {
				mx = c;
			}
		}
	}

	cout << ans << "\n";

	vector<int> vec;
	for (int i = m; i >= 1; i--) {
		vec.push_back(mx - trace[i][mx]);
		mx = trace[i][mx];
	}

	for (auto it = vec.rbegin(); it < vec.rend(); ++it) cout << *it << " ";
}