프로그래머스 : 카드게임

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42896

프로그래머스

문제 설명 

카드 더미가 있는데 왼쪽 오른쪽으로 나뉘어 있음.

왼쪽 카드는 조건없이 버릴수있고 오른쪽 카드는 왼쪽카드와 같이 버리거나         ---(1)

왼쪽카드에 적힌 수> 오른쪽카드 에 적힌 수 일 때만 버릴 수있다.                    ---(2)

점수는 (2)의경우에만 오른쪽 카드에 적힌 수만 큼 휙득 .. 

 

알고리즘 ..

DP 로 가야될꺼같아서 DP 로 풀었당 어렵당 .. :/

 

코드

#include<iostream>
#include<algorithm>
#include <string>
#include <vector>
 
using namespace std;
vector<int> a;  // L
vector<int> b;   //R
int Size;
int dp[2002][2002];
int func(int L, int R) {
    if (L == Size || R == Size) return dp[L][R]; //한쪽 카드를 다버리면 끝 ~ 
    if (dp[L][R] != 0) return dp[L][R]; 
    
        dp[L][R] = max(func(L + 1, R), func(L + 1, R + 1)); //왼쪽만 버리거나 둘다버리거나
        if (a[L] > b[R]) {
            dp[L][R] = max(dp[L][R], func(L, R + 1) + b[R]);//오른쪽만 버리고 점수휙득.
        }
        return dp[L][R];
 
}
 
 
int solution(vector<int> left, vector<int> right) {
    a = left;    
    b = right;
    Size = a.size();
    int answer = func(0, 0);
    return answer;
}