백준 2662번 기업투자

문제 링크 : https://www.acmicpc.net/problem/2662

문제풀이

사용한 알고리즘 : DP

(1) 코드 7~8

 'dp[x][k] : 1이상~x이하 기업에 k원을 투자하여 얻을 수 있는 최대 이익' 이라고 설정했습니다.

 최종 얻는 최대 이익은 dp[M][N] 일 것입니다.

(2) 코드 9~11

 최대 이익을 얻기 위해 각 기업에서 얼만큼 투자를 했는지 추적하는 배열입니다.

 'path[x][k] : dp[x][k]를 최대로 만들 때, x기업에 투자하는 금액' 이라고 설정하였습니다.

 

 input:

 3 3

 1 5 2 3 

 2 6 5 7

 3 7 9 8

 인 예를 들어보면 다음과 같이 생각할 수 있습니다.

투자금액 \ 기업	1	2	3
1	5	2	3
2	6	5	7
3	7	9	8

 

 DP와 이에따른 path 표를 짜보면 다음과 같습니다.

금액 \ 기업	1		2		3
	dp	path	dp	path	dp	path
1	5	1	5	0	5	0
2	6	2	7	1	8	1
3	7	3	10	2	12	2

 예를 들어 ,

 dp[3][3] = 12

            = 기업 1에 1을 투자해 5 얻음 + 기업 3에 2를 투자해 7 얻음

 입니다.

 따라서 path[3][3] = 2

                        = 1~3기업에서 3원으로 최대 이익을 얻을 때 3기업에 투자한 금액은 2

 입니다.

(3) 코드 22~36

 과정(2)의 생각에 따라 모든 기업, 투자 금액에 따른 dp값과 path값을 구합니다.

 

(4) 코드 38

 구하고자 하는 답은 'dp[M][N] : 1~M 기업에서 N 금액으로 얻는 최대 이익' 입니다.

(4) 코드 39~51

 최대 이익을 얻기 위해 각 기업에 투자한 금액을 각각 구해줍니다.

 탐색은 N기업에서 역으로 진행됩니다.

 각 탐색시, dp값을 구하기 위해 현재 기업에 투자한 금액을 구한 뒤,

 이를 총 투자금액에서 빼주면서 탐색을 진행합니다.

 위의 예를 들면,

 dp[3][3] = 12 이고, path[3][3] = 2 입니다.

 즉 3 기업에 투자한 금액은 2 입니다.

 따라서 다음 탐색에서는 dp[2][3-2] 를 생각합니다.

 dp[2][1] = 5 이고, path[2][1] = 0 입니다.

 즉 2 기업에 투자한 금액은 0 입니다.

 마지막 탐색에서는 dp[1][1-0] 을 생각하겠죠?

 dp[1][1] = 5 이고, path[1][1] = 1 입니다.

 즉 1 기업에 투자한 금액은 1 입니다.

	#include <bits/stdc++.h>
	using namespace std;
	int N, M;
	// company[x][k] : x 회사에 k원 투자할 때 얻는 가치
	int company[22][333];
	// dp[x][k] : x 까지 회사에서 k원으로 얻을 수 있는 최대 가치
	int dp[22][333];
	// 각 기업 투자 액수 추적할 배열
	// path[x][k] : dp[x][k]를 최대로 만드는 x에서 투자한 금액
	int path[22][333];
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) {
	int invest;
	cin >> invest;
	for (int i = 1; i <= M; ++i) cin >> company[i][invest];
	}
	for (int i = 1; i <= M; ++i) { // 모든 기업
	for (int cost = 1; cost <= N; ++cost) { // 모든 투자 금액
	// i 기업에서 j만큼 쓴다고 생각.
	for (int j = 0; j <= cost; ++j) {
	// 이전 dp[i-1][cost-j] 에서 얻은 이익 + i기업에서 j금액으로 얻은 이익
	int val = dp[i - 1][cost - j] + company[i][j];
	if (val > dp[i][cost]) { // 이게 더 이득이면
	// dp 값 최신화
	dp[i][cost] = val;
	// dp[i][cost] 값을 최대로 만드는 i번째 회사 투자금액
	path[i][cost] = j;
	}
	}
	}
	}
	cout << dp[M][N] << '\n';
	vector<int> ans;
	int curr = M;
	int cost = N;
	while (curr > 0) {
	// dp[curr][cost] 를 최대로 만드는 현재 기업에서 투자하는 금액
	int now_invest = path[curr][cost];
	ans.push_back(now_invest);
	// 현재 기업에서 투자한 만큼 빼줌
	cost -= now_invest;
	// 이전 기업
	curr--;
	}
	reverse(ans.begin(), ans.end());
	for (auto it : ans) cout << it << ' ';
	return 0;
	}

view raw BOJ 2662.cpp hosted with ❤ by GitHub