[백준 2552번] [동적 계획법] 기업투자

Approach

이 문제에 대해서 잘 고찰해보면, 어떤 기업이 선택되는 것은 이전 기업에 얼마만큼의 투자했는지에 의해서 결정된다.

따라서 이러한 측면에서 관계식을 통해 표현할 수 있으므로 DP라고 인식해야 한다.

 

Let $dp[i][j]$ : the amount of maximum profit when we investing exactly $j$ until considering $i$'th element

$dp[i][j] = \underset{k \in R, \forall k \in [0,j]}{max}(dp[i - 1][j - k] + b[i][k])$

 

즉, i번째 기업까지를 고려해서 투자할 때, i - 1번째 까지의 투자 데이터를 가지고 있으면 된다. 그렇게 되면 투자 금액이 동일할 때, 최대의 이익이 얼마인지를 위의 점화식을 통해 구할 수 있게 된다.

 

다만, 이 문제에서 가장 중요한 것은 Backtracking(복원)이다.

사실 최대값만 구하면, 어떠한 방법으로 만드는지 중요하지 않고 해당 최대값을 만족시키는 케이스만 찾으면 된다.

(즉, 최대를 만족하는 케이스가 unique하지 않다.)

 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int dp[21][301]; // i번째 기업까지 고려했을 때, 정확히 j만큼의 투자금액을 한 상황에서의 이익

int main(void){
    fastio;
    memset(dp, 0, sizeof(dp));
    int n, m;
    cin >> n >> m;

    vector<int> b[m + 1];

    for(int i = 1; i <= m; i++){
        b[i].push_back(0); // Trash data
    }

    for(int i = 1; i <= n; i++){
        int t;
        cin >> t;
        for(int j = 1; j <= m; j++){
            int v;
            cin >> v;
            b[j].push_back(v);
        }
    }

    for(int i = 1; i <= m; i++){
        for(int j = 0; j <= n; j++){
            for(int k = 0; k <= j; k++){
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + b[i][k]);
            }
        }
    }

    int max_result = -1;
    int max_index;

    for(int i = 0; i <=n; i++){
        if(max_result < dp[m][i]){
            max_result = dp[m][i];
            max_index = i;
        }
    }
    cout << max_result << "\n";
    
    vector<int> result;

    for(int i = m; i > 1; i--){
        for(int j = 0; j <= n; j++){
            if(max_result == dp[i - 1][n - j] + b[i][j]){
                result.push_back(j);
                max_result -= b[i][j];
                n -= j;
                break;
            }
        }
    }

    for(int j = 0; j <= n; j++){
        if(max_result == b[1][j]){
            result.push_back(j);
            break;
        }
    }

    for(int i = result.size() - 1; i >= 0; i--){
        cout << result[i] << " ";
    }
    cout << "\n";
    return 0;
}