[ICPC] 백준 2066 - 카드놀이

www.acmicpc.net/problem/2066

문제 소개

원문은 Double patience라는 게임을 하는데 규칙을 따르면서 랜덤 픽하는 조지가 그게 효율적이지 않다고 까는 매튜와 논쟁을 벌이면서 이 게임을 이길 수 있는 확률을 구하는 것이다.

풀이

놀랍게도 구차원 dp이다. 테이블은 다음과 같다.

 

dp[a][b]...[h][i] := 각 묶음에서 카드가 a장, b장, ... h장, i장 있을 수 있는 확률

 

dp[4][4][4][4][4][4][4][4][4]는 카드가 모두 쌓여있는 초기 상태이기 때문에 1.0으로 두면 된다.

 

카드가 4장씩 9묶음만 있기 때문에 9중첩 반복문을 돌려도 실행 시간이 여유로움을 알 수 있다.

 

카드가 모두 쌓여있는 경우부터 시작해서 규칙에 맞게 카드를 제거할 수 있는 경우를 모두 찾는다.

 

그러면 그 경우의 수만큼 기존 확률에서 나눠질 것이고 카드를 제거한 경우에 해당되는 테이블에 나눠진 확률을 더해주는 연산을 반복하면 마침내 카드를 모두 제거한 dp[0][0][0][0][0][0][0][0][0]의 확률을 구할 수 있다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
using pii = pair<int, int>;
 
double dp[5][5][5][5][5][5][5][5][5];
int deck[9][5];
unordered_map<char, int> mtch;
 
vector<vector<int>> two_choice(vector<int> idx)
{
    vector<vector<int>> ret;
 
    for (int i = 0; i < 9; ++i)
    {
        for (int j = i + 1; j < 9; ++j)
        {
            if (!idx[i] || !idx[j])
                continue;
            
            vector<int> nxt(9);
            
            if (deck[i][idx[i]] == deck[j][idx[j]])
            {
                nxt[i] = nxt[j] = -1;
                ret.push_back(nxt);
            }
                
        }
    }
 
    return ret;
}
 
int main()
{
    dp[4][4][4][4][4][4][4][4][4] = 1.;
    mtch['6'] = 6, mtch['7'] = 7, mtch['8'] = 8, mtch['9'] = 9, mtch['T'] = 10, mtch['J'] = 11, mtch['Q'] = 12, mtch['K'] = 13, mtch['A'] = 14;
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    (cout << fixed).precision(6);
 
    for (int i = 0; i < 9; ++i)
    {
        for (int j = 1; j <= 4; ++j)
        {
            string tmp;
            cin >> tmp;
            deck[i][j] = mtch[tmp[0]];
        }
    }
 
    for (int a = 4; a >= 0; --a)
    {
        for (int b = 4; b >= 0; --b)
        {
            for (int c = 4; c >= 0; --c)
            {
                for (int d = 4; d >= 0; --d)
                {
                    for (int e = 4; e >= 0; --e)
                    {
                        for (int f = 4; f >= 0; --f)
                        {
                            for (int g = 4; g >= 0; --g)
                            {
                                for (int h = 4; h >= 0; --h)
                                {
                                    for (int i = 4; i >= 0; --i)
                                    {
                                        if (dp[a][b][c][d][e][f][g][h][i] == 0.)
                                            continue;
                                        
                                        vector<int> cur{a, b, c, d, e, f, g, h, i};
 
                                        auto tmp = two_choice(cur);
 
                                        double prob = dp[a][b][c][d][e][f][g][h][i] / tmp.size();
 
                                        for (int idx = 0; idx < tmp.size(); ++idx)
                                        {
                                            vector<int> next = cur;
                                            for (int jdx = 0; jdx < 9; ++jdx)
                                                next[jdx] += tmp[idx][jdx];
                                            
                                            dp[next[0]][next[1]][next[2]][next[3]][next[4]][next[5]][next[6]][next[7]][next[8]] += prob;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
 
    cout << dp[0][0][0][0][0][0][0][0][0];
}