[ 백준 ] 10835번 - 카드게임 (C++)

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

10835번: 카드게임

 

 

[ 문제풀이 ]

 

1. dp[ 2000 ][ 2000 ] 배열을 선언하고 -1로 초기화해 줍니다.

 

2. 현재 카드더미가 왼쪽이 left번 째, 오른쪽이 right번 째일 때 점수의 최댓값을 dp [ left ][ right ]에 저장합니다.

 

3. 왼쪽 카드만 버릴 때와 왼쪽 카드와 오른쪽 카드를 동시에 버릴 때는 점수를 얻지 못하고, 왼쪽 카드보다 오른쪽 카드의 숫자가 작을 때 오른쪽 카드만 버릴 수 있고, 오른쪽 카드만 버렸을 때 점수를 얻을 수 있으므로 다음과 같은 점화식을 통해 최댓값을 구합니다.

 

ret = max(dfs(left + 1, right), dfs(left + 1, right + 1));

if (l[ left ] > r[ right ]) {
ret = max(ret, dfs(left, right + 1) + r[ right ]);
}

 

4. dp[ 0 ][ 0 ]을 출력합니다.

 

[ 소스코드 ]

#include<iostream>
 
using namespace std;
 
int N;
int dp[2000][2000];
int l[2000];
int r[2000];
int ans;
 
int dfs(int left, int right)
{
    if (left == N || right == N) return 0;
    if (dp[left][right] != -1) return dp[left][right];
 
    int& ret = dp[left][right];
    ret = 0;
    
    ret = max(dfs(left + 1, right), dfs(left + 1, right + 1));
 
    if (l[left] > r[right]) {
        ret = max(ret, dfs(left, right + 1) + r[right]);
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dp[i][j] = -1;
        }
    }
 
    for (int i = 0; i < N; i++) {
        cin >> l[i];
    }
 
    for (int i = 0; i < N; i++) {
        cin >> r[i];
    }
 
    cout << dfs(0, 0);
}