[Algorithm]Baekjoon 2662번 :: 기업투자

https://www.acmicpc.net/problem/2662

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n, m;
int investmentInfo[22][302] = { 0 };
int dp[22][302] = { 0 }; // 
int route[22][302] = { 0 };
 
int DFS(int companyIndex, int leftMoney)
{
    if (companyIndex > m) return 0;
 
    int& result = dp[companyIndex][leftMoney];
    if (result != -1) return result;
 
    result = 0;
 
    for (int i = 0; i <= leftMoney; ++i)
    {
        int profit = investmentInfo[companyIndex + 1][i];
        int temp = DFS(companyIndex + 1, leftMoney - i) + profit;
 
        if (temp > result)
        {
            result = temp;
            route[companyIndex][leftMoney] = i;
        }
     }
 
    return result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i) // 돈
    {
        for (int j = 1; j <= m+1; ++j) // 회사
        {
            int num;
            if (j == 1)
            {
                cin >> num;
                continue;
            }
 
            cin >> investmentInfo[j-1][i];
        }
    }
 
    memset(dp, -1, sizeof(dp));
 
    cout << DFS(0, n) << endl;
 
    int leftMoney = n;
 
    for (int i = 0; i < m; ++i)
    {
        int index = route[i][leftMoney];
        cout << index << " ";
        leftMoney -= index;
    }
}
 
 
 

 

최대값을 구하는것뿐만 아니라 경로도 구해야하는 문제이다.

처음엔 dp테이블을 3차원으로 해서 풀었는데, 통과는 했다만 시간이 오래걸리길래 다른사람풀이를 봤더니 충분히 2차원으로도 가능해서 다시 고민해서 작성해봤다.

 

계속 발견되는 나만의 문제긴한데, 선택지를 dp테이블에 포함시키는 습관이 자꾸 있는것같다. 

물론 있어도 해결은 된다, 다만 불필요한 탐색과 메모리를 더 먹어서 문제이고, 만약 실제 코딩테스트때 메모리제한이 타이트할 경우 통과도 못할 수 있다.

 

dp테이블은 다음과 같다.

dp[i][j] = i번째 회사에서 j원 남았을 때 최대이익.

 

문제에서 인풋은 회사마다 각 금액별로의 이익이 아니라, 각 금액별기준으로 회사의 이익으로 들어오기 때문에 인풋을 잘 받아야 한다.

나는 회사를 기준으로 하는게 더 머리속으로 연상하기 편해서 회사별 이익으로 배열에 저장했고, dp테이블도 마찬가지이유로 1차원을 회사인덱스, 2차원을 남은금액으로 했다.

 

이후는 많이 어려울 건 없다. 

각 회사인덱스와 남은금액이 독립적인 루트가 되서, 해당 루트에서 다음 회사의 각 금액별로 반복문을 돌렸을 때 최대 이익을 얻을 수 있는 값을 리턴해주면 된다.

이 때, 경로까지 구해야 하는 문제이기 때문에 각 루트에서 최대값을 주는 투자금액 (반복문에서의 i)를 저장해주면 된다.

 

이후 최대이익 출력 후, 각 루트마다 최대값을 리턴했던 투자금액이 저장되어있으므로 해당 투자금액을 출력 후, 남은돈에서 투자금액만큼 빼준다음 다시 다음 인덱스꺼를 출력해주는 식으로 해주면 된다.