[BOJ][백준] 2066:카드놀이

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

2066번: 카드놀이

한 벌의 트럼프 카드 중 36장의 카드를 이용하여 하는 놀이가 있다. 각각의 카드들은 4장씩, 9개의 그룹으로 나눠서 놓이게 된다. 카드를 놓을 때에는 앞면(무늬와 숫자가 적혀 있는 면)이 보이도록 놓게 된다. 각각의 카드는 두 개의 문자로 나타낼 수 있는데, 하나는 숫자(6~9, T, J, Q, K, A)와 무늬를 나타내는 문자(S, D, H, C)로 이루어진다.

이 놀이의 목적은 이 카드들 중에서 두 장의 카드를 들어내는 과정을 18번 반복하여 모든 카드를 들어내는 것이다. 카드를 들어낼 때에는 서로 다른 그룹에 있는 카드들로 들어내야 하며, 각 그룹의 제일 위에 있는 카드만을 들어낼 수 있다. 또한 아무렇게나 들어낼 수 있는 것이 아니라, 숫자가 같은 경우만 들어낼 수 있다.

예를 들어 9개의 그룹의 제일 위에 놓여 있는 카드들이 차례로 KS, KH, KD, 9H, 8S, 8D, 7C, 7D, 6H라고 해 보자. 이 경우에는 들어낼 수 있는 조합이 5가지 있는데, 각각 (KS, KH), (KS, KD), (KH, KD), (8S, 8D), (7C, 7D)이다.

당신은 이 놀이를 처음 해 보기 때문에 들어낼 수 있는 조합이 여러 개 있는 경우에는 그중 하나를 랜덤 하게, 그리고 같은 확률로 택해서 들어내기로 하였다. 위의 예에서는 다섯 가지의 경우를 택할 확률이 각각 0.2가 되는 것이다. 이와 같이 놀이를 진행했지만, 당신은 매우 높은 확률로 이 놀이에 성공(모든 카드를 들어냄)하게 되었다. 당신은 이를 이상하게 느끼고, 카드들의 초기 상태가 주어졌을 때, 이 놀이에 성공할 확률을 구해보려 한다.

카드들의 초기 상태가 주어졌을 때, 이 놀이에 성공할 확률을 구해내는 프로그램을 작성하시오.

입력

9개의 줄에 4개의 문자열로 각각의 카드에 대한 정보가 주어진다. 각각의 줄에는 각각의 그룹에 있는 카드들이, 밑에 있는 카드부터 위에 있는 카드 순서대로 주어진다.

출력

첫째 줄에 놀이에 성공할 확률을 출력한다. 절대/상대 오차는 10^6까지 허용한다.

 

---

이제부터 포스팅하는 문제들은 제목에 알고리즘 분류를 안적기로했습니다. 제목에 스포일러를 떡하니 두는 느낌이라..

이 문제는 dp문제입니다. 그냥dp도 아닌 map을 쓰는 dp문제입니다. 사실 dp는 메모이제이션을 하는 방법이 여러 가지죠. 보통은 그냥 배열을 선언해도 되지만 이러한 특수의 경우에서는 map자료구조를 사용하거나, 심지어 deque를 사용하는 dp도 존재합니다. 여기서는 map을 메모이제이션으로 활용하는데, map을 썼을 때 장점은 string이나 vector <int> 형태도 메모이제이션 할 수 있고, 심지어 구조체를 선언해서 자신의 입맛대로 캐시질을 하는데 활용할 수 있습니다. 하지만 단점으로는, 시간 복잡도가 크게 증가한다는 점입니다. 그냥 증가가 아니라 엄청나게 증가한다는 건데, 이 시간 복잡도는 아직 찾지 못했습니다. 종 만북에서도 구체적인 시간 복잡도보다는 최대한 사용을 지양하도록 명시가 되어있고요. 하지만 이문제에서 우리는 size가 9인 vector를 선언할 것이고, 부분 문제도 많이 나뉘지 않는(배열의 각 요소가 최대 4) 형태이기 때문에 map을 사용할 수 있는 것입니다. dp점화식을 짜기는 어렵지 않습니다. 각 카드의 위치를 알려주는 vector <int>를 선언하고, 0번째 카드는 4번째(위)에 위치해있고, 1번째 카드는 4번째(위)에 위치 .... 의 정보를 입력해주면 됩니다.

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
string card[10][5];
map<vector<int>, double>cache;

bool done(vector<int>&v) {
	for (int i = 1; i < 10; i++)
		if (v[i] != 0)return false;
	return true;
}

double f(vector<int>now) {
	if (done(now))return 1.0;

	if (cache.find(now) != cache.end()) return cache[now];
	double&ret = cache[now];
	ret = 0.0;
	vector<pair<int, int>> canSelect;
	for (int i = 1; i < 10; i++)
		for (int j = i + 1; j < 10; j++)
			if (now[i] != 0 && now[j] != 0 && card[i][now[i]][0] == card[j][now[j]][0]) {
				canSelect.push_back({ i,j });
			}
	if (canSelect.empty()) return ret = 0.0;
	for (auto i : canSelect) {
		int idx1 = i.first, idx2 = i.second;
		vector<int>next = now;
		next[idx1]--, next[idx2]--;
		ret += f(next)*(1.0 / (double)canSelect.size());
	}
	return ret;
}


int main()
{
	for (int i = 1; i <= 9; i++)
		for (int j = 1; j <= 4; j++)cin >> card[i][j];
	vector<int>start(10, 4);
	cout << f(start);
}

vector <pair <int, int>>canSelect 배열에 내가 선택할 수 있는 짝들을 모두 모아 두었습니다, 확률 계산을 할 때 size가 사용될 겁니다. map을 이용한 메모이제이션이 어색하고 처음 보시는분들도 계실텐데, cache에 방문한적이 있는지 확인하는

if (cache.find(now) != cache.end()) return cache[now];

이 조건문을 제외하고는 평소의 메모이제이션 방식과 동일합니다. vector<int>가  key값으로 들어가는게 이질적이게 보이지만, 이 기술은 꽤 유용하게 쓰이는편입니다. 실제로 이문제는 map을 쓰지않으면 배열을 [4][4][4][4][4][4][4][4][4]로 선언해야하는데, 메모리도 이 방식보다 클 뿐더러 코드도 보기에 깨끗하지않습니다. 제가 dp문제를 풀면서 map으로 메모이제이션 쓴 문제가 두세 개 정도 되는 거 같은데, 문제를 찾으면 밑에 추천 문제로 업데이트를 해두겠습니다.