10835번 카드게임

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

처음에 단순 백트래킹으로 풀다가 시간 초과 났다.

그래서 다른 분의 코드를 보니 cache를 사용한 것에 힌트를 얻어

구현해보았다.

cache를 깜빡하고 있었다.

#include <bits/stdc++.h>
 
using namespace std;
 
int n, cache[2002][2002];
 
vector<int> l, r;
 
int simulation(int left_idx, int right_idx)
{
    if (left_idx == n || right_idx == n) return 0;
    
    int &get = cache[left_idx][right_idx];
 
    if (get != -1) return get;
 
    get = 0;
 
    get = max(simulation(left_idx + 1, right_idx), simulation(left_idx + 1, right_idx + 1));
 
    if (l.at(left_idx) > r.at(right_idx)) get = max(get, simulation(left_idx, right_idx + 1) + r.at(right_idx));
 
    return get;
}
 
int main(void)
{
    memset(cache, -1, sizeof(cache));
 
    int num = 0;
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &num);
        l.push_back(num);
    }
 
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &num);
        r.push_back(num);
    }
 
    cout << simulation(0, 0) << '\n';
 
    return 0;
}