[프로그래머스 4] 카드게임 (C/C++) (★★)

#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
 
vector<int> a; // left
vector<int> b; // right
int dp[2010][2010] = {0};
 
int solve(int leftIdx, int rightIdx)
{
    if(leftIdx == a.size() || rightIdx == b.size())
    {
        return 0;
    }
    
    if(dp[leftIdx][rightIdx] != -1)
    {
        return dp[leftIdx][rightIdx];
    }
    
    // 1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
    dp[leftIdx][rightIdx] = max(solve(leftIdx+1, rightIdx), solve(leftIdx+1, rightIdx+1));
    
    // 2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
    if(a[leftIdx] > b[rightIdx])
    {
        dp[leftIdx][rightIdx] = max(dp[leftIdx][rightIdx], solve(leftIdx, rightIdx+1) + b[rightIdx]);
    }
    
    return dp[leftIdx][rightIdx];
}
 
int solution(vector<int> left, vector<int> right) 
{
    a = left;
    b = right;
    
    memset(dp, -1, sizeof(dp));
    
    int answer = solve(0, 0); 
    
    return answer;
}