BOJ)2662 기업투자

문제: icpc.me/2662

투자 가능금액과 기업의 수가 주어지고 해당 기업에 x원만큼 투자했을 때 얻을 수 있는 이득 y가 주어질 때 최대 이익을 출력하는 문제이다.

최대 이익은 다이나믹 프로그래밍을 통하여 구해줄 수 있다. 

테이블 dp[val][pos]의 정의는 "val 만큼 투자 가능할 때 pos번째 기업부터 n번째 기업까지 투자하여 얻을 수 있는 최대 이익"이 될것이다. 4

점화식은 dp[val][pos] = for(i=1~k) max(dp[val-i][pos+1]+a[i][pos]) 가 될것이다. 여기서 a[x][y]는 y번째 기업에 x만원을 투자하여 얻을 수 있는 돈이다.

이 때 역추적을 해주기 위하여 최댓값의 갱신이 일어날 때 마다 역추적 배열을 갱신해준 뒤 함수 종료후 백트래킹 해주면 된다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 987654321
using namespace std;
int k, n, x, y, z;
int a[301][21];
int dp[301][21];
pair<int, int> back[301][21];
int func(int val, int pos) {
    if (val == 0)
        return 0;
    if (pos > n)
        return -INF;
    if (val < 0)
        return -INF;
    int &ret = dp[val][pos];
    if (ret != -1)return ret;
    for (int i = 0; i <= k; i++) {
        if (ret < func(val - i, pos + 1) + a[i][pos]) {
            ret = func(val - i, pos + 1) + a[i][pos];
            back[val][pos] = { val - i,pos + 1 };
        }
    }
    return ret;
}
int main(){
    memset(dp, -1, sizeof(dp));
    scanf("%d%d", &k, &n);
    while (scanf("%d", &x) != EOF) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[x][i]);
    }
    printf("%d\n", func(k, 1));
    x = k, y = 1;
    for (int i = 1; i <= n; i++) {
        printf("%d ", x - back[x][y].first);
        int cx = x;
        x = back[x][y].first;
        y = back[cx][y].second;
    }
    return 0;
}