백준 17953번 디저트 C++ (골드5)

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

 

캐시테이블을 cache[디저트 번호][날짜][전과 같은 디저트 여부] 로 만들어서 dp로 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m;

vector<vector<int>> v;
vector<vector<vector<int>>> cache;

int dp(int dessert, int day, int isSameDessert)
{
    int& val = cache[dessert][day][isSameDessert];
    if (val != -1) return val;
    val = 0;
    int curr = v[dessert][day];
    if (isSameDessert == 1) curr /= 2;
    if (day == n)
    {
        return val = curr;
    }
    for (int i = 1; i <= m; i++)
    {
        if (i == dessert)
        {
            val = max(val, dp(i, day + 1, 1) + curr);
        }
        else {
            val = max(val, dp(i, day + 1, 0) + curr);
        }
    }
    return val;
}

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

    cin >> n >> m;
    v = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
    cache = vector<vector<vector<int>>>(m + 1, vector<vector<int>>(n + 1, vector<int>(2, -1)));
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> v[i][j];
        }
    }
    int ans = dp(0, 0, 0);
    cout << ans;
}