KOI(한국정보올림피아드) 2015년 중등부2번 카드게임

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

#include 
#include 
using namespace std;
#define MAX_N 2000

int N;
int left[MAX_N+1], right[MAX_N+1];
int dp[MAX_N+1][MAX_N+1];

void solve() {
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]); //왼쪽카드만 버렸을 때와 양쪽 카드를 모두 버렸을 때 중에서 최댓값
            if(right[j] < left[i]) //왼쪽카드보다 오른쪽카드에 적힌 수가 더 클때
                dp[i][j] = max(dp[i][j], dp[i][j-1]+right[j]); //오른쪽카드를 버렸을 때와 버리지 않을 떄의 최댓값
        }
    }
    printf("%d", dp[N][N]);
}

int main() {
    scanf("%d", &N);
    //최하단 카드는 1번에 넣고 최상단 카드는 N번으로
    for(int i=N; i>0; i--) scanf("%d", &left[i]);
    for(int i=N; i>0; i--) scanf("%d", &right[i]);

    solve();
    return 0;
}