백준[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;

}