백준10835 카드게임

작성일 | In

문제 링크

  • http://icpc.me/10835

문제 출처

  • 2015 KOI 초등부3, 중등부2

사용 알고리즘

  • DP

시간복잡도

  • O(n2)

풀이

dp[i][j]를 왼쪽에서 i개, 오른쪽에서 j개 버린 경우의 정답이라고 정의합시다.
왼쪽의 카드는 left, 오른쪽의 카드는 right 배열에 저장하고, 정답을 찾는 함수는 solve(i, j)로 정합시다.
left[i] > right[j] 인 경우에는 오른쪽을 버린 결과인 dp[i][j] = solve(i, j+1) + right[j] 입니다.
나머지의 경우에는 왼쪽만 버리거나, 양쪽을 버린 결과의 최댓값인 dp[i][j] = max(solve(i+1, j), solve(i+1, j+1)) 입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> Left, Right;
int dp[2020][2020];

int solve(int i, int j){
	if(i>=n || j>=n) return dp[i][j] = 0;
	if(dp[i][j] != -1) return dp[i][j];
	if(Left[i] > Right[j]){
		dp[i][j] = max(dp[i][j], solve(i, j+1)+Right[j]);
	}
	dp[i][j] = max(dp[i][j], solve(i+1, j));
	dp[i][j] = max(dp[i][j], solve(i+1, j+1));
	return dp[i][j];
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; Left = vector<int>(n); Right = vector<int>(n);
	for(int i=0; i<n; i++) cin >> Left[i];
	for(int j=0; j<n; j++) cin >> Right[j];
	memset(dp, -1, sizeof(dp));
	cout << solve(0, 0);
}