[백준] 10835번 카드 게임

10835번: 카드게임

처음엔 완전 탐색으로 풀었었는데 경우의 수가 너무 많기 때문에 당연히 시간 초과됐었다.

그래서 다른 방법들도 시도하다 안 돼서 검색해보니

Top-Down 방식으로 푸는 DP 문제였다.

 

문제의 나와 있는 규칙을 정리해보면

 

1. 왼쪽 카드의 값 > 오른쪽 카드의 값 인 경우

1) 오른쪽 카드만 버릴 수 있다

2) 왼쪽 카드만 버릴 수 있다

3) 양쪽 카드를 모두 버릴 수 있다

 

2. 왼쪽 카드의 값 <= 오른쪽 카드의 값 인 경우

1) 왼쪽 카드만 버릴 수 있다

2) 양쪽 카드를 모두 버릴 수 있다

 

이렇게 크게 두 가지 경우가 나온다.

 

현재 왼쪽 더미와 오른쪽 더미의 맨 위에 있는 카드를 각각 i번째, j번째 카드라 하고

이차원 배열 dp를 만들어서

dp[i][j] = i번째, j번째 카드가 보일 때 얻을 수 있는 점수의 최댓값

이라고 생각할 때,

 

1. 왼쪽 카드의 값 > 오른쪽 카드의 값 인 경우

1) 현재 오른쪽 카드의 값 + 오른쪽 카드를 버렸을 때 얻는 점수의 최댓값

2) 왼쪽 카드를 버렸을 때 얻는 점수의 최댓값

3) 양쪽 카드를 모두 버렸을 때 얻는 점수의 최댓값

 

이 세 가지 경우 중 가장 큰 값을 dp[i][j]에 저장한다.

식으로 나타낸다면

dp[i][j] = max(B[j] + dp[i][j+1], max(dp[i+1][j], dp[i+1][j+1]))

이렇게 될 수 있는데

여기서 굳이 세 가지 경우를 다 비교하지 않아도

가장 큰 값은 B[j]를 더한 값이라는 것을 명백히 알 수 있다.

즉 유일하게 점수를 얻는 1)의 경우가 최댓값이므로

dp[i][j] = B[j] + dp[i][j+1]

으로 식을 바꿔준다.

 

2. 왼쪽 카드의 값 <= 오른쪽 카드의 값 인 경우

1) 왼쪽 카드를 버렸을 때 얻는 점수의 최댓값

2) 양쪽 카드를 모두 버렸을 때 얻는 점수의 최댓값

 

이 두 가지 경우 중 가장 큰 값을 dp[i][j]에 저장하는 식은

dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])

이다.

이 경우는 둘 다 점수를 얻지 않아서 둘 중에 더 큰 값이 무엇인지 모르기에

이 식은 그대로 놔둔다.

 

위의 식들을 Top-Down 방식답게 재귀 함수로 구현해준다.

이때, 양쪽 더미 중 한쪽이라도 남는 카드가 없는 경우 종료시키고

dp[i][j]에 이미 계산된 값이 들어있을 경우 다시 계산할 필요 없으므로 종료시켜야 한다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int A[2001], B[2001], dp[2001][2001];
int N;
int CardGame(int i, int j) {
	if (i == N || j == N) return 0; //한 쪽이라도 empty면 종료
	else if (dp[i][j] != -1) return dp[i][j]; //한 번 방문한 곳은 다시 방문할 필요 없다

	if (A[i] > B[j]) return dp[i][j] = B[j] + CardGame(i, j + 1); //1번 경우
	else return dp[i][j] = max(CardGame(i + 1, j), CardGame(i + 1, j + 1)); //2번 경우
}

int main() {
	cin >> N;
	for (int t = 0; t < 2; t++) {
		for (int n = 0; n < N; n++) {
			if (!t) cin >> A[n];
			else cin >> B[n];
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << CardGame(0, 0);
	return 0;
}