BOJ 10835번 카드게임

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

github : https://github.com/junho0956/Algorithm/blob/master/10835/10835/%EC%86%8C%EC%8A%A4.cpp

 

재귀를 통해 쉽게 해결할 수 있었습니다.

dp를 0이 아닌 -1같은 가능성 없는 값으로 초기화하는 작업을 들이는 습관을 가져야겠습니다.

 

조건에서 오른쪽 더미에 있는 카드가 왼쪽 더미에 있는 카드보다 작을 경우 오른쪽 더미의 카드 점수를 더하라고 했으므로 재귀에서 조건을 다음과 같이 두 가지 경우의 수로 나누어 주었습니다

 

=> 오른쪽 더미에 있는 카드가 왼쪽 더미에 있는 카드보다 작을 경우

1) 오른쪽 카드만큼 더하고 오른쪽 더미 인덱스를 늘린다

2) 왼쪽 카드 인덱스를 늘린다

3) 왼쪽, 오른쪽 카드 인덱스를 늘린다

=> 그 외

1) 왼쪽 카드 인덱스를 늘린다

2) 왼쪽, 오른쪽 카드 인덱스를 늘린다

 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
#define maxi 987654321
int N;
int lpile[2001];
int rpile[2001];
int dp[2001][2001];
 
int dfs(int left, int right) {
    if (left >= N || right >= N) return 0;
 
    int& res = dp[left][right];
    if (res!=-1) return res;
 
    int ans = 0;
    if (lpile[left] > rpile[right]) ans = max(dfs(left, right + 1) + rpile[right], max(dfs(left + 1, right), dfs(left + 1, right + 1)));
    else ans = max(dfs(left + 1, right), dfs(left + 1, right + 1));
 
    return res = ans;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < N; i++) cin >> lpile[i];
    for (int i = 0; i < N; i++) cin >> rpile[i];
 
    cout << dfs(0,0);
    return 0;
}