백준, boj) 2662. 기업투자 ( C / C++)

1. 문제 링크

https://www.acmicpc.net/problem/2662

2662번: 기업투자

 

2. 문제 개요

어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 투자는 만원 단위로 할 수 있으며, 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다.

 

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

 

3. 문제 힌트

이 문제를 Brute force방식으로 푼다면 시간 복잡도가 어떻게 나올까?

m개의 기업에 대해서, n만큼의 숫자를 m개의 기업에 적절히 분배할 때의 나올 수 있는 모든 조합의 수가 될 것이다.

여튼 엄청 많다..

 

그러면 이거를 어떻게 줄일 수 있을까?

DP를 사용하여 의미 없는 값들을 없애고, 최댓값들만 갖고 가보자.

 

최댓값을 구하려면 결국은 완전 탐색을 해야 한다. 하지만 이것을 어쩌면 효율적으로 정말 탐색할 수 있을지 알아보자.

 

(1) 최댓값 구하기

기업이 2개이고 투자하는 금액이 1원이라고 생각해보자.

그럼 최댓값은 무엇이 될까? (A기업에 1원, B기업에 0원) 아니면 (A기업에 0원, B기업에 1원) 중 큰 것이 될 것이다.

 

기업이 2개이고, 투자하는 금액이 3원이라고 생각해보자. (A기업, B기업)이라고 했을 때,

최댓값은 (0,3) or (1,2) or (2,1) or (3,0)이 된다.

 

이번에는 기업이 2개이고 투자하는 금액이 n원이라고 생각해보자.

최댓값은 (0, n) (1, n-1), (2, n-2)......(n-1, 1), (n,0)중 가장 큰 값이 된다.

 

그렇다면 기업이 3개 이상일 때는 어떻게 비교해야 할까? 곰곰이 생각해보자

 

(2) 투자 금액 구하기

투자금액은 끝에서부터 역으로 추적해간다.

기업이 m개 있고 n원을 투자했을 때의 최댓값을 찾았을 때, 누구와 매칭 한 것이 최댓값인지 저장한다.

예를 들어서 m번째 기업에서 n원을 투자했을 때의 최댓값이 2원, n-2원 을 투자한 것이 최대라고 가정하면, n-2원을 저장해 두는 것이다.

그럼 n원에서 n-2원을 빼면 2원이 나오고 m-1번째 기업에서 2원은 누구와 매칭 했는지 또 계산하면 역으로 추적이 가능해진다.

 

n원이 아닐 때를 보자, n=100인데, m-1번째 기업에서 50원을 투자했을 때 누구와 매칭 되었는지 알아내 보자.

만약에 (10, 40) 원을 투자해서 50원이 최대가 되었다 라고 하면, trace[50][m-1]은 40을 갖고 있는 것이다.

그렇다면 현재 투자한 금액인 50원에서 40원을 빼면 10원이 나오고, trace[10][m-2]로 추적하면 되는 것이다.

 

(3) DP 설계

DP 배열은 어떻게 설계해야 할까?

모든 수를 완전 탐색할 수는 없고, 이전 정보를 사용해서 이번 정보를 구해야 한다.

 

기업의 수가 m개이고 투자금액이 n원일 때의 최댓값을 DP로 정의하자.

DP[n][m] : 기업의 수가 m개이고 투자금액이 n원일 때의 최댓값.

 

이렇게 구현하면 항상 2개의 기업에 대해서만 처리하듯이 구현하면 된다.

ex) m이 4일 때, (A+B+C)에서의 최댓값을 알 고 있고, 새로 들어오는 기업 D에 대한 최댓값만 구하면 됨.

 

4. 문제 풀이

(3) 번인 힌트에서 거의 다 서술한 것 같다.

DP를 사용하면 항상 1번에 최대 n, 즉, 1,2,3,4..... 300의 합까지만 비교하면 된다. 따라서 시간 복잡도는 O(n*m)이 된다.

이렇게 되는 이유는 최댓값이 아닌 값을 모두 들고 가면 어차피 최댓값이 나오지 않기 때문에 그 값들은 비교할 필요가 없어진다는 것이다.

 

5번의 코드란에서 Bottom-up과 Top-down을 모두 구현해보았다.

Bottom-up에서는 dp를 굳이 여러 개 만들 필요 없어서 2개로만 구현했다.

 

top-down에서는 전부다 구현했다.

 

결국 완전 탐색인데 어떻게 효율적으로 정말 탐색할 건지가 DP문제들의 요점인 것 같다.

 

5. 코드

(1) Bottom-up

#include <cstdio>
#include <vector>
using namespace std;

int n, m;
int v[301][21];
int dp[301][2];
int ans[301][21];
vector<int> ret;
int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; ++i) {
		int money;
		scanf("%d", &money);
		for (int j = 0; j < m; ++j)
			scanf("%d", &v[money][j]);
	}

	for (int i = 0; i <= n; ++i) {
		dp[i][0] = v[i][0];
		ans[i][0] = i;
	}

	for (int i = 1; i < m; ++i) {
		for (int j = 0; j <= n; ++j)
			for (int k = 0; k <= j; ++k) {
				if (dp[j][1] <= dp[j - k][0] + v[k][i]) {
					dp[j][1] = dp[j - k][0] + v[k][i];
					ans[j][i] = k;
				}

			}


		for (int i = 0; i <= n; ++i) {
			dp[i][0] = dp[i][1];
			dp[i][1] = 0;
		}
	}

	printf("%d\n", dp[n][0]);
	int val = n;
	for (int i = m - 1; i >= 0; --i) {
		ret.push_back(ans[val][i]);
		val = val - ans[val][i];
	}

	for (int i = ret.size() - 1; i >= 0; --i)
		printf("%d ", ret[i]);

	return 0;
}

 

(2) top-down

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n, m;
int val[301][21];
int trace[301][21];
int dp_table[301][21];

void tracert(int cur, int com)
{
	if (com == 0)	return;
	
	tracert(cur - trace[cur][com], com - 1);
	printf("%d ", trace[cur][com]);
	
	return;
}
int dp(int cur, int com)
{
	//base
	if (com == 0)	return 0;

	int &cache = dp_table[cur][com];
	if (cache != -1)return cache;

	for (int k = 0; k <= cur; ++k) {
		int value = dp(k, com - 1) + val[cur - k][com];
		if (cache < value) {
			cache = value;
			trace[cur][com] = cur - k;	//com 기업에서는 cur-k원을 선택하면 최적.
		}
	}
	
	
	return cache;
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i){
		int money;
		scanf("%d", &money);
		for (int j = 1; j <= m; ++j)
			scanf("%d", &val[money][j]);
	}
	memset(dp_table, -1, sizeof(dp_table));

	printf("%d\n", dp(n, m));
	tracert(n, m);
	return 0;
}

 

 

6. 결과 사진

Bottom up

Top-down

 

지적, 댓글 언제나 환영입니다~