[백준 10835] 카드게임 DFS, DP 풀이..

# 문제링크

www.acmicpc.net/problem/10835

10835번: 카드게임

DFS 로 모든 경우의 수를 돌려보려고 했는데, 시간 초과가 나서 DP로 풀었습니다. 

 

# 제출 코드 

 

// DFS

 

#include <iostream>
using namespace std;

int N;
int left_card[2000];
int right_card[2000];

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> left_card[i];
	for (int i = 0; i < N; i++)
		cin >> right_card[i];

}
int max_n = 0;
void DFS(int left, int right,  int sum) {
	if (left == N || right == N) {
		if (max_n < sum) max_n = sum;
		return;
	}
	// 오른쪽 카드 버리는 경우 -> 오른쪽 카드 만큼 얻음
	if (right_card[right] < left_card[left]) {
		DFS(left, right + 1, sum + right_card[right]);
	}
	else {
		// 왼쪽 카드 버리는 경우 -> 얻는 점수 없음
		DFS(left + 1, right, sum);
		// 둘 다 버리는 경우 -> 얻는 점수 없음
		DFS(left + 1, right + 1, sum);
	}
}
int main() {
	Input();
	DFS(0, 0, 0);
	cout << max_n;
	return 0;
}

 

// DP

 

#include <iostream>
#include <cstring>
using namespace std;

#define MAXN 2000

int N;
int left_card[MAXN + 10];
int right_card[MAXN + 10];
int M[MAXN][MAXN];

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> left_card[i];
	for (int i = 0; i < N; i++)
		cin >> right_card[i];
}
int DP(int left, int right) {
	if (left == N || right == N) return 0;

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

	M[left][right] = 0;
	// 오른쪽 카드 버리는 경우 -> 오른쪽 카드 만큼 얻음
	if (right_card[right] < left_card[left]) {
		M[left][right] += right_card[right] + DP(left, right + 1);
	}
	else {
		M[left][right] += max(DP(left + 1, right), DP(left + 1, right + 1));
	}
	return M[left][right];
}
int main() {
	Input();

	memset(M, -1, sizeof(M));
	cout << DP(0, 0);;
	return 0;
}