[C/C++] 백준 - 10835번 : 카드게임

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

10835번: 카드게임

문제

지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다. 

이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다. 

다음 예는 세 장 씩 두 더미의 카드를 가지고 게임을 시작하는 경우이다

카드 순서왼쪽 더미오른쪽 더미

1	3	2
2	2	4
3	5	1

이 경우, 우선 오른쪽 카드 2가 왼쪽 카드 3보다 작으므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 모두 버리거나, 규칙 (2)에 따라 오른쪽 카드만 버릴 수 있다. 만약 오른쪽 카드만 버리는 것으로 선택하면, 2만큼 점수를 얻고 오른쪽 카드 2는 버린다. 이제 오른쪽 더미의 제일 위 카드는 4이고 이는 왼쪽 카드 3보다 크므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 둘 다 버릴 수 있다. 만약 둘 다 버리는 것으로 선택하면, 이제 왼쪽 카드는 2가 되고 오른쪽 카드는 1이 된다. 이 경우 다시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 왼쪽 카드만 버리는 것으로 선택하면 이제 왼쪽 카드는 5가 되고 오른쪽 카드는 1이 된다. 이 경우에도 역시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 오른쪽 카드만 버리는 것으로 선택하면 1만큼 점수를 얻고 오른쪽 카드 1은 버린다. 이제 오른쪽 더미에는 남은 카드가 없으므로 규칙 (3)에 따라 게임이 끝나며 최종 점수는 2+1=3이 된다.

두 더미의 카드가 주어졌을 때, 게임을 통해 얻을 수 있는 최종 점수의 최댓값을 출력하는 프로그램을 작성하시오. 위 예에서 최종 점수의 최댓값은 7이다.

 

---

문제를 읽어보면 모든 경우의 수를 확인하여 최대값 점수를 찾아야하는 문제라는 것을 알 수 있다.

근데 조건으로 주어진 제한을 보면 카드는 왼쪽 / 오른쪽 모두 2000장이 최대로 주어질 수 있는데 우리가 행할 수 있는 3가지 행동에 대해 완전탐색으로 시간 내 통과가 가능할까?

 

카드의 개수가 적으면 통과가 가능하겠지만 2000장이 되면 2000^3의 연산이 들어가게 되기 때문에 양쪽을 모두 봐야하는 것을 고려하지 않더라도 이미 시간초과가 발생한다.

 

그렇기 때문에 이 문제는 완전탐색 + 메모이제이션으로 중복되는 경우는 피해야한다. 즉, 동적계획법을 이용하여 문제를 해결해야한다.

 

직관적으로 동적계획법을 적용하기 위해 메모이제이션을 어떻게 할까 생각해보면

남은 왼쪽카드의 개수 / 남은 오른쪽카드의 개수 + 남아있는 카드들을 어떤 방식으로 처리(ex, 1 / 2 / 3번)

위 처럼 단순하게 동적계획법을 수행할 수 있다.

 

근데 생각해보면 남아있는 왼쪽 카드의 개수 / 남아있는 오른쪽 카드의 개수에 결국 어떤 방식으로 사용하든 최대값을 저장해야 정답을 구할 수 있으므로 메모이제이션을 적용할 때 남아있는 카드들을 어떤 방식으로 처리할지는 고려하지 않아도 된다.

 

-> 따라서 메모이제이션은 간단하게 [남아있는 왼쪽 카드의 개수][남아있는 오른쪽 카드의 개수]로 적용하여 여기에 최대값을 저장해주는 형태로 진행한다. 그리고 이미 진행해서 최대값을 저장해두었던 곳에 다시 한 번 확인을 해야할 경우에는 진행하지 않고 값만 반환받는 동적계획법 해결법을 적용하여 해결한다.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <climits>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000009
#define endl '\n'
#define ENDL cout << endl

using namespace std;

int N;
int cache[2000 + 1][2000 + 1];

void split(vector<int>& v, string str) {
	string temp;
	for (auto t : str) {
		if (t == ' ') {
			v.push_back(stoi(temp));
			temp.clear();
		}
		else {
			temp += t;
		}
	}
	v.push_back(stoi(temp));
}

int path(vector<int>& lhs, vector<int>& rhs, int lhsIndex, int rhsIndex) {
	if (lhsIndex == lhs.size() || rhsIndex == rhs.size()) return 0;
	int& ret = cache[lhsIndex][rhsIndex];
	if (ret != -1) return ret;

	ret = 0;
	ret = max({ ret, path(lhs, rhs, lhsIndex + 1, rhsIndex), path(lhs, rhs, lhsIndex + 1, rhsIndex + 1) });
	if (lhs[lhsIndex] > rhs[rhsIndex]) {
		ret = max(ret, path(lhs, rhs, lhsIndex, rhsIndex + 1) + rhs[rhsIndex]);
	}
	return ret;
}

int solution(vector<int>& lhs, vector<int>& rhs) {
	memset(cache, -1, sizeof(cache));
	return path(lhs, rhs, 0, 0);
}

void input() {
	cin >> N;
	cin.ignore();
	string l, r;
	vector<int> lhs, rhs;

	getline(cin, l);
	getline(cin, r);

	split(lhs, l);
	split(rhs, r);

	cout << solution(lhs, rhs) << endl;
}

int main() {
	fastio;
	input();

	return 0;
}