[백준 2662] 기업 투자

문제 링크

참고자료 : 마포코딩박님 블로그

문제

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

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

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

풀이 방법

문제처럼 기업이 2개만 주어졌을 때는 단순한 덧셈으로만 코드를 돌려도 문제가 없다.(0,4), (1,3), (2,2), (3,1), (4,0) 이런식으로..
근데 만약 기업이 3개라면, 4개라면, 30개라면?
절대 단순한 덧셈이 될 수 없다.

이렇게 생각을 해보자.

이렇게 생각해보면, dp[M][N] = MAX(dp[M][N], Path[M][N] + dp[M-1][N-Path[M][N]])
이러한 점화식이 나오게 된다.
물론 이 점화식을 곧이곧대로 쓰진 않고, 좀 더 직관적으로 코딩할 것이다. 아이디어가 이렇다는 뜻.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N,M;
int company[21][301];
int dp[21][301];
int path[21][301];

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

    for(int i = 1; i<=N; i++){
        int invest;
        cin >> invest;
        for(int j = 1; j<=M ; j++)
            cin >> company[j][invest];
    }

    for(int i = 1; i<=M; i++){  // 모든 기업.
        for (int cost = 1; cost <= N; cost++){ // 모든 금액.

            for(int j = 0; j<=cost; j++){   // i 기업에서 j 금액 만큼 투자한다고 생각해보자.

                int val = dp[i-1][cost-j] + company[i][j];  // i기업 뺴고 j금액 만큼 다른회사들이랑 투자한거 + i기업의 j금액 투자.
                if (val > dp[i][cost]){ // 그게 더 높으면 dp를 바꾸자.
                    dp[i][cost] = val;
                    path[i][cost] = j;
                }
            }
        }
    }

    cout << dp[M][N] << '\n';
    // 이 아래는 별로 중요하지 않다. 그냥 단순하다.
    vector<int> answer;
    int curr = M;
    int cost = N;
    while(curr>0){
        int invest = path[curr][cost];
        answer.push_back(invest);

        cost -= invest;
        curr--;
    }
    reverse(answer.begin(),answer.end());
    for(auto it:answer)
        cout << it << " ";
}