백준 2662번: 기업투자 [C++]

작성일 | In
골드 II 골드 II

문제

기업투자
배낭 문제인데 좀 특별한 배낭 문제입니다.

풀이

기업 1부터 기업 $x$까지 투자했을때 최대 이익을 기업 1부터 기업 $x+1$까지 투자했을때 최대 이익을 구하는데 쓸 수 있는 DP, 그 중에서도 배낭 문제입니다.

구해야 할 답

구해야 할 답은 총 2가지입니다.

  1. 최대 이익
  2. 최대 이익을 위해 각 회사에 투자해야 할 금액

1. 최대 이익

배낭의 크기 제한(투자 금액), 고를 수 있는 물건(기업), 골랐을 때의 가치(이익)이 주어져 있습니다.
먼저, 수열 몇개를 정의해 줍시다.
$profit_{ij}$는 i번째 기업에 j만큼 투자했을 때 얻는 이익입니다.
$dp_{ij}$는 i번째 기업까지 총 j만큼 투자했을 때 얻는 최대 이익입니다.
그러면 점화식을 세워 풀 수 있습니다.
$dp_{ij} = max(dp_{ij},\ dp_{i-1\ j-k} + profit_{ik})\ (0 \leq k \leq j)$

말로 풀어서 쓰자면, 투자했던 금액 중 k만큼을 철회하고, 그 금액만큼 i번째 기업에 투자하는게 더 이득이라면 그렇게 하겠다는 것입니다.

2. 각 회사별 투자 금액

투자 금액도 DP를 이용해서 구합니다.
배열 하나를 정의해 줍시다.
$answer_{ij}$는 i번째 기업까지 총 j만큼 투자했을 때 최대 이익을 얻는 방법입니다.
$answer_{24} = \{\ 0\ 4\ \}$와 같은식으로 배열의 값을 갖습니다. 이 수들 중 x번째 수는 x번째 기업에 투자할 금액을 나타냅니다.
그렇다면 $answer_{ij}$도 DP를 이용해 구할 수 있습니다. 만약 $dp_{ij}$의 값이 갱신된다면, $answer_{ij} = answer_{i-1\ j-k} + \{\ k\ \}$ 입니다.

코드로 나타내면 아래와 같이 나타낼 수 있겠습니다.

1
2
3
4
// vector<int> answer[m+1][n+1];

answer[i][j] = answer[i-1][j-k];
answer[i][j].push_back(k);

코드

i, j는 짧아서 좋지만 너무 헷갈린다는 단점이 있어 대신 corp, usedMoney라는 변수명을 사용했습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

int profit[21][301]; // profit[corp][cost];
int dp[21][301]; // dp[corp][usedMoney];
vector<int> answer[21][301]; // corp, usedMoney에서의 답


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n, m;
    cin >> n >> m;

    for (int i = 0 ; i < n ; i++) {
        int cost;
        cin >> cost;
        for (int corp = 1 ; corp <= m ; corp++) {
            cin >> profit[corp][cost];
        }
    }


    for (int corp = 1 ; corp <= m ; corp++) {
        for (int usedMoney = 0 ; usedMoney <= n ; usedMoney++) {
            for (int cost = 0 ; 0 <= usedMoney-cost ; cost++) {
                if (dp[corp][usedMoney] <= dp[corp-1][usedMoney-cost] + profit[corp][cost]) {
                    dp[corp][usedMoney] = dp[corp-1][usedMoney-cost] + profit[corp][cost];
                    answer[corp][usedMoney] = answer[corp-1][usedMoney-cost];
                    answer[corp][usedMoney].push_back(cost);
                }
            }
        }
    }

    cout << dp[m][n] << '\n';

    for (int i : answer[m][n]) {
        cout << i << ' ';
    }


    return 0;
}

여담

contribute image 골드 II는 아직 쉽지 않네요…

백준 2662번: 기업투자 [C++]