백준(BOJ) 1344 축구 **

# DP

조금 버벅거리면서 풀었던 dp문제였다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 10005
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef deque<int> di;

int a,b;
double ans=0,p[2][2],dp[20][20][20];
bool tf[20]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0};

int main() {
    scanf("%d%d",&a,&b);
    p[0][0]=(double)a/100,p[0][1]=1-p[0][0];
    p[1][0]=(double)b/100,p[1][1]=1-p[1][0];
    dp[0][0][0]=1;
    for(int i=0;i<=17;i++)
        for(int j=0;j<=17;j++)
            for(int k=0;k<=17;k++)
            {
                dp[i+1][j+1][k+1]+=dp[i][j][k]*p[0][0]*p[1][0];
                dp[i+1][j+1][k]+=dp[i][j][k]*p[0][0]*p[1][1];
                dp[i+1][j][k+1]+=dp[i][j][k]*p[0][1]*p[1][0];
                dp[i+1][j][k]+=dp[i][j][k]*p[0][1]*p[1][1];
            }
    for(int i=0;i<=18;i++)
        for(int j=0;j<=18;j++)
            if(tf[i]||tf[j])
                ans+=dp[18][i][j];
    printf("%.6lf",ans);
    return 0;
}