백준 10835번 카드게임 C++

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

 

오른쪽 카드가 왼쪽 카드보다 작은 경우와, 큰 경우 두 가지로 나누어서 문제를 해결하였다.

오른쪽 카드가 왼쪽 카드보다 작은 경우는

1. 오른쪽 카드의 점수를 얻고 오른쪽 카드를 빼는 경우

2. 왼쪽 카드를 빼는 경우

3. 양쪽 카드를 빼는 경우

이 세 가지 중 큰 값을 구했고

반대의 경우에는

1. 왼쪽 카드를 빼는 경우

2. 양쪽 카드를 빼는 경우

이 두 가지 중 큰 값을 구했다.

 

그리고 같은 지점을 계속 탐색할 수 있기 때문에 시간 초과나 스택 오버플로우가 발생할 수 있다.

그렇기 때문에 메모이제이션 기법을 통해 dp배열에 방문한 곳을 저장해서 바로 빠져나올 수 있게 작성하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n;
int c_Left[2001];
int c_Right[2001];
vector<vector<int>> dp(2001, vector<int>(2001, -1));

int solve(int left, int right) {
	if (left > n || right > n) {
		return 0;
	}

	if (dp[left][right] != -1) return dp[left][right];

	if (c_Left[left] > c_Right[right]) {
		dp[left][right] = max(solve(left, right + 1) + c_Right[right], max(solve(left + 1, right + 1), solve(left + 1, right)));
	}
	else {
		dp[left][right] = max(solve(left + 1, right + 1), solve(left + 1, right));
	}

	return dp[left][right];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> c_Left[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> c_Right[i];
	}
	int ans = solve(1, 1);
	cout << ans;
};