[BOJ 2662]기업투자

[BOJ]2662-기업투자

예전부터 시도해왔던 문제인데 이제서야 풀었다. 전형적인 dp문제로, 각 기업별로 투자금별 수익금이 제시되고 한정된 금액으로 최대의 수익을 내기 위해서 어느 기업에 얼마만큼 투자를 해야하는지 묻는 문제이다. dp테이블의 의미는 dp[a][b]=c -> 금액 a원을 b번째 기업까지 투자했을 때 만들 수 있는 최대 금액 c원이다. 나 같은 경우에 최대 수익금을 찾는 구현은 그럭저럭 잘 했으나 각 기업에 얼마만큼 투자를 했는지 찾는 과정의 구현이 조금 애를 먹었다. dp loop를 돌리는 동안에 별도로 add[][]라는 배열을 마련해서 이전 상태에서 현재상태의 얼마를 더 투자해서 현재의 금액이 되었는지를 저장하는 역할이다. 그리고 최대 금액을 알아낸 상태에서 역순으로 금액을 빼가면서 추적해가며 얼마를 투자했는지를 찾아가는 방법을 사용했다. 그리고 이 문제를 풀면서 또 하나의 교훈은 dp테이블에서 열과 행을 잘 설정해야 구현할 때 헷갈리지 않는다는 점이다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define SIZE 309
 
int dp[SIZE][22],benefit[SIZE][22],add[SIZE][22];
int main(){
    int n,m;    scanf("%d %d",&n,&m);
 
 
    for(int i=0 ; i<n ; i++){
        int cur;    scanf("%d",&cur);
        for(int j=1 ; j<=m ; j++){
            scanf("%d",&benefit[cur][j]);
        }
    }
 
    for(int i=0 ; i<=n ; i++){
        for(int j=1 ; j<=m ; j++){
            for(int k=0 ; k<=i ; k++){
                int last=dp[i][j],now=dp[i-k][j-1]+benefit[k][j];
                if(last<now){
                    dp[i][j]=now;
                    add[i][j]=k;
                }
            }
        }
    }
 
    int total=0;
 
    for(int i=0 ; i<=n ; i++)
        total=max(total,dp[i][m]);
 
    vector<int> v;
    int tgt=total;
 
    for(int i=m ; i>=1 ; i--){
        for(int j=n ; j>=0 ; j--){
            if(tgt==dp[j][i]){
                int idx=add[j][i];
                tgt-=benefit[idx][i];
                v.push_back(idx);
                break;
            }
        }
    }
 
    reverse(v.begin(),v.end());
   
    printf("%d\n",total);
    for(int here:v) 
        printf("%d ",here);
 
    return 0;
}