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