[백준]기업투자(2662)

문제 링크 : [백준]기업투자(2662)

2662번: 기업투자

 

문제 설명

기업별로 투자 금액 별 수익금이 주어집니다.

N원을 투자하여 최대로 수익을 얻을 수 있는 금액과 어떤 기업에 얼마를 투자해야 하는지 구하세요.

입력

N(투재 금액, 1 <= N <= 300)

M(기업 갯수, 1 <= M <= 20)

A B_i(투자 정보, O원을 B_i기업에 투자하였을 때의 수익) 

4 2
1 5 1
2 6 5
3 7 9
4 10 15

 

출력

15
0 4

 

카테고리

#DP

 

시간 복잡도 상한

O(M²N)

 

해결 방법

1. 특정 금액으로 최대 수익을 얻어야 하는 문제입니다.
2. DP[i][j] = i번째 기업까지 j원을 투자하여 얻을 수 있는 최대 수익금이라고 정의하면
3. DP[i][j] = max(DP[i-1][j-k]+B[i][k])(0 < k < j) 로 구할 수 있습니다.
4. 그러나 이것뿐만 아니라 어떤 기업에 얼마를 투자해야하는지를 알아야 합니다.
5. DP[i][j]를 구할 때, k의 값을 저장합니다.
6. 즉 i번째 기업까지 j원을 투자하여 최대 금액을 얻는 상황에서 i번째 기업에 얼마를 투자해야 하는지 저장합니다.
7. 이 정보를 가지고, 역추적하여 출력하면 됩니다.

시간복잡도

O(MN²)

코드

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,d[21][301],e[21][301],v[21][301],i,j,k,s,a[21];
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){scanf("%*d");for(j=1;j<=m;j++)scanf("%d",d[j]+i);}
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            for(k=0;k<=j;k++){
                if(e[i][j]<e[i-1][j-k]+d[i][k]){
                    e[i][j]=e[i-1][j-k]+d[i][k];
                    v[i][j]=k;
                }
            }
        }
    }
    printf("%d\n",e[m][n]);
    for(j=n,i=m;i;i--){
        a[i]=v[i][j];
        j-=v[i][j];
    }
    for(i=1;i<=m;i++)printf("%d ",a[i]);
}