[BOJ] 주식왕 동호

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <climits>
#include <math.h>
using namespace std;
using ll = long long;
using ld = long double;
ll MOD = 1'000'000'000 + 7;

using namespace std;


int c, d, m;


int stocks[51][11];


// dp table을 만들 때 며칠인지 데이터가 무조건 필요하다.
// day가 10까지고, stock이 50까지고,
// dp table이 가져야할 것이 뭘까?
// 그리고 어디서 상태 전이가 발생해서 이거를 점화식으로 나타낼 수 있는가?
// day, 어떤 stock을 몇 개 샀는지 사실 이거는 bottom-up으로 할거면 상관이 없긴한데.
// 이를 최대한 시간 안에 만들려면 어떤 것을 다 구매하거나 뭐 이런 것처럼 아예 하나를 선택할 때 바로 몇 개를 사야되는게 좋은지를 증명해야됨.
// 자체로 greedy로 가게되면 문제가 되는게 논리적인 측면에서 조금의 증명으로 조금 엄밀해질 필요가 있따.

// 깊게 들어가면서 남은 돈을 다 투자하도록 만드는 방법도 있음.
// 그냥 for문으로 해결할 수 있는 방법 없을까?
// 일단 3중까지는 가능할거 같은데 4승까ㅣㅈ도 가능하네


int dp[500'001];




int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> c >> d >> m;
    
    for(int i = 0; i < c; i++){
        for(int j = 0; j < d; j++){
            cin >> stocks[i][j];
        }
    }
    
    // 아 각 날마다 가지고 있는 돈에 대한 dp로 가져와서 진행하면 되겠다
    // dp[i] = max(dp[i], dp[i- 아 싸발 일어났따
    // think!
    for(int i = 1; i < d; i++){
        for(int _ = 0; _ <= 500'001; _++) dp[_] = 0;
        
        for(int j = 0; j < c; j++){
            for(int k = stocks[j][i-1]; k < m+1; k++){
                dp[k] = max(dp[k], dp[k - stocks[j][i-1]] + stocks[j][i] - stocks[j][i-1]);
                
            }
            
        }
        m+= dp[m];
    }
    
    
    cout << m;
    return 0;
}