BOJ 10835 - 카드게임 ( 2015 KOI 초등, dp )

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

 

왼쪽 더미 i번째, 오른쪽 더미 j번째를 보고 있을 때 다음으로 선택할 수 있는 경우의 수가 최대 3가지 이다.

 

bfs로 풀어야되나? 싶었는데 i,j 외에 여태 얻은 값을 세번째 상태로 계속 넘겨줘야 해서 visited공간이 부족하고, map으로 구현하기도 비효율적이다.

 

dp로 풀기로 해서 점화식을 짜 봤는데 깔끔하게 짜 졌다. 이후 코드로 옮기기만 했다.

 

 

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

int n, a[2000], b[2000], dp[2000][2000];

int f(int i, int j) {
	if (i == n || j == n) return 0;

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

	if (a[i] > b[j]) return ret = b[j] + f(i, j + 1);
	else return ret = max(f(i + 1, j + 1), f(i + 1, j));
}

int main() {
	cin >> n;
	
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i];
	
	fill(&dp[0][0], &dp[1999][2000], -1);
	cout << f(0, 0) << '\n';
}