[10835] 카드게임

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

10835번: 카드게임

 

접근:

• 점수를 위해서는 모두 버리는 것보다 오른쪽 카드 더미를 버리는 행위를 선택해야 합니다.
• 오른쪽 카드가 더 크다면, 왼쪽 카드만 버리거나 모두 버리는 것 중 큰 결과를 갖는 행위를 선택합니다.
• 카드 인덱스로 위 행위를 재귀 함수화하면, 중복되는 경우들이 있기 때문에 동적할당법을 사용합니다. (2000*2000)

 

코드:

#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int N;
int L[2000], R[2000];
int cache[2000][2000]; // 캐시

// i = 왼쪽 카드 더미 인덱스
// j = 오른쪽 카드 더미 인덱스
int findMax(int i, int j) 
{
	if (i >= N || j >= N) return 0; // 하나라도 끝나면 종료한다.

	int& ret = cache[i][j];
	if (ret != -1) { return ret; }

	if (L[i] > R[j]) return ret = R[j] + findMax(i, j + 1);
	else return ret = max(findMax(i + 1, j + 1), findMax(i + 1, j)); // 모두 버리거나, 왼쪽만 버리기
}

int main()
{
	memset(cache, -1, sizeof(cache));
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> L[i];		
	}
	for (int i = 0; i < N; i++)
	{
		cin >> R[i];
	}

	cout << findMax(0, 0) << "\n";
	return 0;
}