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

문제

어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 않은 경우는 당연히 얻게 되는 이익도 없다. 예를 들어서, 한 투자가가 4만원을 갖고 두 개의 기업들에 각각 만원 단위로 투자했을 경우 얻을 수 있는 이익은 다음과 같다.

위의 경우 만일, 기업 A에 1만원, 기업 B에 3만원을 투자하는 경우 투자가가 얻는 이익은 14만원(5만원+9만원)이다. 4만원을 투자해서 가장 많은 이익을 얻을 경우 기업 B에만 4만원을 투자하는 경우로서 이때의 이익은 15만원이다. 여기서 투자가는 한 기업에 돈을 나누어 투자할 수는 없다.

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

입력

첫째 줄에 투자 금액 N과 투자 가능한 기업들의 개수 M이 주어진다. (1 ≤ N ≤ 300, 1 ≤ M ≤ 20)

둘째 줄부터 N개의 줄에 투자액수와 각 기업이 투자가에게 주는 이익이 주어진다. 투자 금액은 항상 1보다 크거나 같고, N보다 작거나 같고, 같은 투자 금액이 두 번 이상 주어지는 경우는 없다. 즉, i번 줄에 주어지는 투자 금액은 i-1만원이다.

출력

첫 줄에 얻을 수 있는 최대 이익을 출력하고, 둘째 줄에는 각 기업에 투자한 액수를 출력한다. 최대 이익은 231보다 작다.

풀이

평소 재귀적으로 동적계획법을 설계하는 것을 좋아하지만 이 문제는 반복적 동적계획법으로 푸는 것이 더 쉬워보여 이 방법을 택했다.
dp[i][j]는 투자금 j를 가지고 0~i번째 기업까지 투자했을 때 얻을 수 있는 최대 이익이다. 이는 투자금 j-k를 가지고 i-1번째 회사까지 투자했을 때 얻을 수 있는 최대 이익 + i번째 회사에 k만큼 투자했을 때 이익이다. 여기서 k를 0~j까지 늘려가며 최대 이익을 찾으면 된다.
dp[i][j] = max(dp[i][j], corp[i][k]+dp[i-1][j-k])
하지만 이 문제는 여기서 끝나는것이 아니라 각 회사에 투자한 금액을 구해야한다. 따라서 maxN[i][j]에 투자금액 k를 기록한다. maxN[m-1][money]에는 마지막회사에 투자한 금액 k가 담길 것이고 maxN[m-2][money-k]에는 그 직전회사에 투자한 금액이 담길 것이다. 이와 같은 방식으로 금액을 역추적해 출력하면 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int money,m;
int corp[20][301];
int dp[20][301];
int maxN[20][301];
int ans[20];

void reconstruct(int cp, int m){
  if (cp == -1) return;
  // cp기업에 투자한 금액
  ans[cp] = maxN[cp][m];
  reconstruct(cp-1, m-ans[cp]);
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> money >> m;

  for (int i=1; i<=money; i++)
    for (int j=0; j<=m; j++){
      int a;
      cin >> a;
      if (j==0) continue;
      corp[j-1][i] = a;
    }

  for (int i=0; i<m; i++){
    for (int j=1; j<=money; j++){
      if (i == 0) {
        dp[i][j] = corp[i][j];
        maxN[i][j] = j;
      }
      else{
        int ret = 0;

        for (int k=0; k<=j; k++){
          if (ret < corp[i][k]+dp[i-1][j-k]){
            ret = corp[i][k]+dp[i-1][j-k];
            maxN[i][j] = k;
          }
        }
        dp[i][j] = ret;
      }
    }
  }
  
  cout << dp[m-1][money] << endl;

  reconstruct(m-1,money);

  for (int i=0; i<m; i++)
    cout << ans[i] << " ";
}