백준 2662번 : 기업투자

  기업에 투자했을 때 보장된 이득을 볼 수 있다니! 이 얼마나 꿈같은 얘기인가~ 게다가 수익률도 기본적으로 100%가 넘는다...! 와! 샌즈! 와! 나도 할래 ㅠㅠ

---

  풀이

  만약 최대 이익만을 출력하는 문제였다면 조금 더 쉬웠을 것이다. 약간 응용된 배낭(냅색) 문제 정도? 하지만 각 기업에 투자한 액수를 출력하라는 문제 때문에 코드가 길어지고 구현이 조금 복잡해졌다. 일단 최대 금액을 구하는 것부터 해보자.

---

  최대 금액 구하기

  평소처럼 dp를 잘 정의하자.

 

dp[n][m] : n만원으로 1번 기업부터 m번 기업까지 투자할 때 얻을 수 있는 최대 이익

 

  dp[n][m-1]인 상황에서 m번째 회사에 invest 만큼의 금액을 투자하면 dp [n + invest][m]이 된다.

 

dp [n + invest][m] = dp [n][m - 1] + menu [invest][m]

menu [invest][m] : invest원을 m번째 회사에 투자했을 때 얻는 이익

 

  이때 투자 가능한 금액(invest)은 총 투자 금액 N을 넘을 수 없으므로 0 이상 N - n 이하일 것이다. 우리가 구하고자 하는 것은 최대 이익이므로 다른 루트로 온 값과 비교해서 큰 값을 채택해야 한다.

 

dp [n + invest][m] = max(dp [n + invest][m] ,  dp [n][m - 1] + menu [invest][m])

 

  이런 방식으로 dp를 계산하면 dp [n][m]이 구하고자 하는 최대 이익이 될 것이다.

---

  각 기업에 투자한 액수 구하기

  문제는 여기다. 어떻게 각 기업에 투자한 금액을 구하지? 그 루트를 어떻게 추적하지? 나는 이 문제를 해결하기 위해 dp_invest라는 2차원 어레이를 하나 더 만들었다.

 

dp_invest [n][m] : dp [n][m]를 구할 때 최종적으로 결정된 m번째 회사의 투자 금액(invest)

 

  정의가 좀 복잡하긴 한데 max함수를 통해 dp [n][m]에 어떤 값이 할당될 때 최종적으로 할당될 때의 invest 값을 저장해두는 것이다. 이를 위해 max함수를 쓰지 않고 if문을 통해 직접 비교하는 방식으로 바꿨다.

---

  출력하기

  출력은 stack을 사용했다. 최종 목적지는 dp [n][m]이라는 것은 알지만 거기까지의 도달 과정은 역추적할 수밖에 없는 상황이었기 때문에 LIFO(Last In First Out)인 stack을 사용하면 기록과 출력을 편하게 할 수 있을 것이라고 생각했기 때문이다.

  dp_invest [n][m]의 값이 invest였다면 invest를 stack에 넣어둔다. 그다음 dp_invest [n-invest][m-1]을 stack에 넣는 과정을 반복한다.

#include <iostream>
#include <stack>

using namespace std;

int n, m;
int menu[302][21];
int dp[302][21];
int dp_invest[302][21];
stack<int> invests;

int main()
{
    cin >> n >> m;
    
    int trash;
    for(int i = 1; i <= n ; i++)
    {
        cin >> trash;
        for(int j = 1; j <= m; j++)
        {
            cin >> menu[i][j];
        }
    }
    
    for(int comp = 1; comp <= m; comp++)
    {
        for(int value = 0; value <= n; value++)
        {
            for(int invest = 0; invest <= n-value; invest++)
            {
                if(dp[value+invest][comp] < dp[value][comp-1] + menu[invest][comp])
                {
                    dp[value+invest][comp] = dp[value][comp-1] + menu[invest][comp];
                    dp_invest[value+invest][comp] = invest;
                }
            }
        }
    }
    
    cout << dp[n][m] << "\n";
    
    int invest;
    int value = n;
    int comp = m;
    while(comp != 0)
    {
        invest = dp_invest[value][comp];
        invests.push(invest);
        value -= invest;
        comp -= 1;
    }
    
    while(invests.empty() == false)
    {
        cout << invests.top() << " ";
        invests.pop();
    }

    return 0;
}