축구 C++ - 백준 1344

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

이 문제는 풀고 정말 기뻤던 문제이다.

사실 이 문제를 풀려고 한 이유가 dp 경험 쌓으려고 푼 문제인데,

조합으로 풀어서 AC를 받았다.

$P_A$를 A팀이 간격 내 득점할 확률,

$P_B$를 B팀이 간격 내 득점할 확률이라고 하자.

먼저 소수로 득점하지 않는 경우는 득점 개수에 따라 나뉜다.

0,1,4,6,8,9,10,12,14,15,16,18개를 득점할 시 소수로 득점하지 않는다.

따라서 위 개수만큼을 득점할 확률을 편의상 $\Sigma P_{A,B}$라 하자.

적어도 한 팀이 소수로 득점하려면 위 집합들의 여집합이기에,

$1-{(\Sigma P_A*\Sigma P_B)}$가 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

double calp(double p, int n){
    double result=1;
    int cnt=18-n;
    while(n--){
        result*=p;
    }
    while(cnt--){
        result*=(1-p);
    }
    return result;
}

ll cb(int n, int m){
    long long result=1;
    int cnt=m;
    while(cnt--){
        result*=n;
        n--;
    }
    cnt=m;
    while(cnt--){
        result/=m;
        m--;
    }
    return result;
}

int notP[]={0,1,4,6,8,9,10,12,14,15,16,18};
double pA,pB;
double pnotPA=0, pnotPB=0;

int main(){
    cout.precision(8);
    cin >> pA >> pB;
    pA/=100;
    pB/=100;
    for(int i=0;i<12;i++){
        pnotPA+=calp(pA,notP[i])*cb(18,notP[i]);
        pnotPB+=calp(pB,notP[i])*cb(18,notP[i]);
    }
    cout << 1-pnotPA*pnotPB;
    return 0;
}