문제 링크
문제
티어: 골드 1
알고리즘: dp
한 벌의 트럼프 카드 중 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까지 허용한다.
풀이
놀이에 성공할 확률을 출력해야 한다.
성공할 확률은 모든 카드를 들어낼 수 있는 모든 경우의 확률 합이 된다.
성공 확률을 구하기 위해서는 당연히 가능한 특정 pair를 선택했을 때 모든 경우에서 전부 들어낼 수 있는지 체크해야 한다.
그런데 단순히 pair를 선택할 수 있는 모든 경우를 탐색한다면 시간 초과가 발생할 것이다.
그래서 dp를 생각해 볼 수 있다. dp를 활용한다면 중복 탐색을 없애야 한다.
여기서에 중복 탐색은 현재 남아있는 카드와 그 배열이 같다면 이는 같은 상태이기 때문에 이 부분을 메모제이션해야 된다.
그러면 전체 상태가 몇 개나 있는지를 세봐야 한다. 모든 상태가 시간 초과 날 정도로 많을 수 있기 때문이다.
모든 상태를 구하기 위해서
가장 밑에 카드 라인부터 보겠다.
각 칸에는 카드가 있을 수 있고, 없을 수 있다. 그래서 이 경우는 2^9개가 된다.
다음 바로 위 카드 라인을 보겠다.
이때 각 칸은 총 3가지 존재한다. 예를 들어 다음과 같다.
- 첫 번째는 카드가 있는 경우다. 카드가 있다면 그 밑 모든 라인 또한 카드가 있어야 한다.
O
O
- 두 번재는 카드가 없는 경우다. 카드가 없다면 그 밑 카드 라인은 있을 수 있고, 없을 수 있다.
X
O
,
X
X
그래서 3가지다.
이런 방식으로 4번 째 라인까지 구해보면
3번 째 라인은 4가지고, 가장 위 라인인 4번 째 라인은 5가지가 된다.
그래서 모든 상태는 5^9개 존재한다.
이제는 각 경우의 수를 dp로 어떻게 표현할 수 있는지를 고민해야 한다.
각 라인마다 다음과 같은 5가지 경우가 존재하기 때문에 (맨 밑 -> 맨 위)
- X X X X
- O X X X
- O O X X
- O O O X
- O O O O
dp는 라인마다 최대 5가지가 존재하는 9차원 배열로 정의할 수 있다.
이후에는 탐색한 상태의 확률을 저장하고, 이후에 중복 탐색을 방지한다면,
시간 복잡도 5^9으로 시간 초과없이 문제를 풀 수 있다.
소스 코드
import java.io.*;
import java.util.*;
class Pair {
int cInd1, cInd2;
Pair(int c1, int c2) {
this.cInd1 = c1;
this.cInd2 = c2;
}
}
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[][] cards = new String[10][5];
for(int i=1; i<=9; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=1; j<=4; j++) {
cards[i][j] = st.nextToken();
}
}
double[][][][][][][][][] dp = new double[5][5][5][5][5][5][5][5][5]; //초기값 0, 불가능 -1
int[] g = new int[10];
for(int i=1; i<=9; i++) {
g[i] = 4;
}
System.out.printf("%.6f\n", findAnswer(g, cards, dp));
}
public static double findAnswer(int[] g, String[][] cards, double[][][][][][][][][] dp) {
if(g[1] == 0 && g[2] == 0 && g[3] == 0 && g[4] == 0 && g[5] == 0 && g[6] == 0 && g[7] == 0 && g[8] == 0 && g[9] == 0) {
return 1.0;
}
if(dp[g[1]][g[2]][g[3]][g[4]][g[5]][g[6]][g[7]][g[8]][g[9]] > 0) {
return dp[g[1]][g[2]][g[3]][g[4]][g[5]][g[6]][g[7]][g[8]][g[9]];
}
if(dp[g[1]][g[2]][g[3]][g[4]][g[5]][g[6]][g[7]][g[8]][g[9]] == -1) {
return 0.0;
}
ArrayList<Pair> pairs = findPairs(g, cards);
if(pairs.size() == 0) {
dp[g[1]][g[2]][g[3]][g[4]][g[5]][g[6]][g[7]][g[8]][g[9]] = -1;
return 0.0;
}
double result = 0.0;
double prob = 1.0 / pairs.size(); //확률
for(int i=0; i<pairs.size(); i++) {
int[] cG = copy(g);
cG[pairs.get(i).cInd1] -= 1;
cG[pairs.get(i).cInd2] -= 1;
double nr = findAnswer(cG, cards, dp);
result += (nr * prob);
}
if(result == 0) {
dp[g[1]][g[2]][g[3]][g[4]][g[5]][g[6]][g[7]][g[8]][g[9]] = -1;
} else {
dp[g[1]][g[2]][g[3]][g[4]][g[5]][g[6]][g[7]][g[8]][g[9]] = result;
}
return result;
}
public static ArrayList<Pair> findPairs(int[] g, String[][] cards) {
ArrayList<Pair> result = new ArrayList<>();
for(int i=1; i<=8; i++) {
for(int j=i + 1; j<=9; j++) {
if(g[i] == 0 || g[j] == 0) {
continue;
}
if(cards[i][g[i]].charAt(0) == cards[j][g[j]].charAt(0)) {
//숫자가 같다면
result.add(new Pair(i, j));
}
}
}
return result;
}
public static int[] copy(int[] arr) {
int[] result = new int[arr.length];
for(int i=0; i<arr.length; i++) {
result[i] = arr[i];
}
return result;
}
}