(C++) - 백준(BOJ) 10835번 : 카드게임

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

10835번: 카드게임

Top-down dp 기본문제였습니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n;
int l[2001],r[2001];
int d[2001][2001];
//두 가지 조건을 고려해야 한다.
//1.왼쪽 카드만 버릴 경우
//2.왼쪽 오른쪽 둘 다 버릴 경우
//3.오른쪽 카드의 수가 왼쪽 카드의 수보다 작은경우 오른쪽을 버릴 수 있다. 버리는 경우 오른쪽 카드에 적힌 수만큼 점수 얻음
//4.남은 카드가 없다면 겜 끝, 최종 점수는 그때까지 얻은 점수
int foo(int left, int right) {
    if (left == n+1 || right == n+1) return 0;
    int &ret = d[left][right];
    if (ret != -1)return ret;
 
    //1.왼쪽 카드만 버릴 경우 얻는 점수는 없다.
    //2.왼쪽 오른쪽 둘 다 버릴 경우 얻는 점수는 없다
    //1,2 경우에서의 점수 최대값
    ret = max(foo(left + 1, right),foo(left+1,right+1));
    //3.오른쪽 카드의 수가 왼쪽 카드의 수보다 작은경우 오른쪽을 버릴 수 있다. 버리는 경우 오른쪽 카드에 적힌 수만큼 점수 얻음
    //4.남은 카드가 없다면 겜 끝, 최종 점수는 그때까지 얻은 점수
    if (l[left] > r[right]) {
        ret = max(ret, foo(left, right + 1) + r[right]);
    }
    //모든 경우의 수를 다해 본 최대값을 반환한다.
    return ret;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> l[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
    }
    memset(d, -1, sizeof(d));
    cout << foo(1, 1) <<'\n';
 
}