백준[10835] - 카드놀이

문제

백준 10835 문제 보기

접근 방법

dfs를 사용해서 경우를 잘 나누면 문제를 해결할 수 있음. 근데 N이 크다보니 메모이제이션 방법으로 중간값을 계속 저장해야 함. 시간 초과가 나지 않을까 걱정했는데 다행히 통과.

코드

#include <iostream>
 
using namespace std;
 
int N;
int box[2001][2001];
int dp[2001][2001];
int sum = 0;
 
int dfs(int leftCard, int rightCard, int num) {
    if (leftCard >= N + 1 || rightCard >= N + 1) {
        return num;
    }
 
    if (dp[leftCard][rightCard] != -1)
        return dp[leftCard][rightCard] + num;
 
    int ret;
    if (rightCard < N + 1 && leftCard < N + 1) {
        ret = dfs(leftCard + 1, rightCard, num);
        ret = max(ret, dfs(leftCard + 1, rightCard + 1, num));
    }
 
    if (box[0][leftCard] > box[1][rightCard] && rightCard < N + 1 && leftCard < N + 1) {
        ret = max(ret, dfs(leftCard, rightCard + 1, num + box[1][rightCard]));
    }
 
    dp[leftCard][rightCard] = ret - num;
    return ret;
 
}
 
int main () {
 
    cin >> N;
 
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < N; j++) {
 
            cin >> box[i][j];
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dp[i][j] = -1;
        }
    }
 
    cout << dfs(0, 0, 0);
 
    return 0;
 
}