BOJ 2662 기업투자

사용한 알고리즘

알고리즘 설명

이 문제는 투자를 통해서 최대 이윤을 얻고자 한다.
DP를 2차원으로 (현재 가지고 있는돈)(현재 회사) 형태의 2차원 DP를 만든다.
DP는 현재 돈과 남은 투자할수 있는 회사를 이용해서 가질수 있는 최대 이윤으로 정의한다.
점화식을 짜면 다음과 같다.
DP(N)(M) = max(cost(i)(M) + dp(N-i)(M-1))
점화식은 다음과 같다. 현재 i원을 사용하여 M 회사를 구매했다고 할때 N-i원과 현재 회사를 제외한 나머지 회사를 이용해 얻을 수 있는 최대 이윤이다.
이와 같이 DP를 구성한 뒤에 이제 각 회사에 얼마씩 투자했는지 알아내야한다.
만약 투자를 하였고 DP(N)(M)를 알고있다고하자.
M번째 회사에 i원을 투자한 것이 최대 이윤이었다고 하자. 그렇다면 아래 식을 만족해야한다.
DP(N)(M) = max(cost(i)(M) + dp(N-i)(M-1))
위를 만족하는 i값, 곧 투자 금액을 출력하면 된다.
여기서 tracking함수는 높은 회사 부터 투자 금액을 찾아 내기 때문에 postorder로 출력하면 순서대로 출력가능하다.

풀이

// baekjoon 2662 yechan
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=301;
const int MAX_M=21;

int N, M;
int cost[MAX_N][MAX_M];
int dp[MAX_N][MAX_M];

int dfs(int money, int company) {
    int &ret = dp[money][company];
    if (money == 0) return ret = 0;
    if (company == 0) return ret = cost[money][company];
    if (ret != -1) return ret;

    ret = 0;
    for (int i=0; i<=money; i++)
        ret = max(ret, cost[i][company] + dfs(money-i, company-1));
    return ret;
}

void tracking(int money, int company) {
    if (company == 0) {
        printf("%d ", money);
        return;
    }
    for (int i=0; i<=money; i++) {
        if (dp[money-i][company-1] == -1) continue;
        if (cost[i][company] + dp[money-i][company-1] == dp[money][company]) {
            tracking(money-i, company-1);
            printf("%d ", i);
            return;
        }
    }
}

int main() {
    memset(dp, -1, sizeof(dp));

    scanf("%d%d", &N, &M);
    for (int i=0; i<N; i++) {
        int c; scanf("%d", &c);
        for (int j=0; j<M; j++)
            scanf("%d", &cost[c][j]);
    }
    printf("%d\n", dfs(N, M-1));
    tracking(N, M-1);
    puts("");
    return 0;
}