2662 기업투자

디피 문제인 건 바로 눈치 챘는데 식 세우는게 너무너무 힘들었다.

 

기업이 여러개일 때 어떻게 할지 엄청 고민했음. 

 

 

 

이건 예시로 잡은 거

 

 

 

예시가 들어왔을 때 최댓값

 

A는 자신의 윗 칸이랑 현재 비용이랑 비교하는 것 같고.. B는 옆 칸이랑 현재비용이랑 비교하면 될 것 같다,,

 

근데 이렇게 하니 최댓값이 안 나오는 것 같다. 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;


int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    vector<vector<int> > v(n + 1, vector<int>(m, 0));
    for (int i = 1; i <= n; i++)
    {
        int tmp;
        scanf("%d", &tmp);
        for (int j = 0; j < m; j++)
        {
            scanf("%d", &v[i][j]);
        }
    }
    
    vector<vector<int> > dp(n + 1, vector<int>(m, 0));
    for (int i = 1; i <= n; i++)
    {
        dp[i][0] = max(dp[i-1][0], v[i][0]);
        for (int j = 1; j < m; j++)
        {
            dp[i][j] = max(dp[i][j-1], v[i][j]);
        }
    }
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            printf("%d ", dp[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

 

ㅠㅠㅠ 이거 돌려보면 아래처럼 나온다. 

3, 2에 10이 아니고 9가 들어갔다. 옆 칸인 7이랑 현재 값인 9랑 비교해서 9가 들어갔구나...

 

이렇게 하면 안 될 것 같다. 

 

---

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;


int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    vector<vector<int> > v(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
    {
        int tmp;
        scanf("%d", &tmp);
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &v[i][j]);
        }
    }
    
    vector<vector<int> > dp(n + 1, vector<int>(m, 0));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            dp[i][j] = max(dp[i][j - 1], v[i][j]);
            for (int k = 1; k <i; k++)
            {
                dp[i][j] = max(dp[i][j], dp[k][j - 1] + v[i - k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            printf("%d ", dp[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

 

 으음....... 최댓값은 구했는데 백트레킹이 문제다...,.,,.,. ㅜㅠㅜㅠㅠㅠㅜㅠㅠㅡㅜ