BOJ 2662 | 기업투자

나는 내가 생각해도 심각한 정도의 DP 부족인데, 최근 열린 Codeforce Div 3에서 간단한 DP 문제를 BFS로 삽질하다가 40분 날리고 충격에 빠졌다.

그래서 곧 있을 SUAPC와 각종 대회들에서 팀원들 발목은 잡지 않으려고 DP 연습을 하고 있다.

월요일부터 기말고사인데 그냥 다 때려치고 코딩만 하고 싶다..

풀이 과정

DP 식을 다음과 같이 세우자.

$DP[i][j] = max(DP[i-1][j-k] + Enterprise[i][k])$

배낭 문제처럼 차례대로 $1$ ~ $T$번째 기업까지 투자를 하면서 DP 식을 세우자.

$DP[i][j]$는 $i$번째 기업에 투자를 하고 투자 총 금액이 $j$원이라는 뜻이다.

그렇다면 $DP[i-1][j-k] + E[i][k]$ 의 모든 값 중 최댓값을 전이하면 된다.

DP를 2차원 배열로 만들었다면 같은 크기의 역추적을 위한 2차원 배열 하나를 더 만들어서 투자금을 기록하자.

$path[i][j]$는 $DP[i][j]$가 업데이트 되었을 때의 $k$ 값을 넣어주면 나중에 $path[i][j] -> path[i][j - path[i][j]] -> ...$ 이런 식으로 역추적 할 수 있다.

따져 보면 $i$번째 기업에 투자한 금액을 $path[i][j]$가 담고 있으므로 역추적이 가능하다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long

#define debug if constexpr (local) std::cout
#define endl '\n'

int dp[25][10005];
int path[25][10005];
int E[25][305];

int main(){
	int N, T; cin >> N >> T;
		
	
	for (int i = 1; i <= N; i++){
		int w; cin >> w;
		for (int j = 1; j <= T; j++) cin >> E[j][w];
	}
	
	for (int i = 1; i <= T; i++){
		for (int j = 1; j <= N; j++){
			for (int k = 0; k <= j; k++){
				if (dp[i-1][j-k] + E[i][k] > dp[i][j]) path[i][j] = k;
				dp[i][j] = max(dp[i][j], dp[i-1][j-k] + E[i][k]);
			}
		}
	}
	
	cout << dp[T][N] << endl;
	vector<int> route;
	
	int cur = N;
	for (int i = T; i >= 1; i--){
		route.push_back(path[i][cur]);
		cur -= path[i][cur];
	}
	reverse(route.begin(), route.end());
	for (auto &i: route) cout << i << ' ';
}