[ BOJ 백준 1344번 - 축구 ] 해설 및 코드

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

사이트 화면 일부 캡쳐

 

목적

축구 경기 90분 동안 적어도 한 팀이 골을 소수로 득점할 확률을 구한다.

 

접근법

1. 총 18개의 간격에서(90분 경기를 5분 간격으로 나눴기 때문..) 소수 아닌 갯수의 골을 넣을 확률 계산

2. 중학교에서 배운 공식을 이용한다.

ex) 득점할 확률이 a이고, 18개 중 4개의 득점을 할 확률 = 18C4 * a^4 * (1-a)^14

3. nCr에 해당하는 조합은 파스칼의 삼각형 공식으로 구한다.

 

#include <iostream>
#include<cmath>
#include<vector>
 
using namespace std;
 
const int N = 19;
vector<int> range({0,1,4,6,8,9,10,12,14,15,16,18});
int C[N];
 
// n==N-1일 때, 𝚗C𝚛 구하기
void initBC(){
    int n=N;
    C[0]=C[1]=1;
    for(int i=2;i<n;++i){
        C[0]=C[i]=1;
        for(int j=i-1;j>0;--j)C[j]+=C[j-1];
    }
}
double solve(){
    
    initBC();
    double a,b;cin>>a>>b;
    a/=100;b/=100;
    
    double Sa=0,Sb=0;
    for(int r:range){
        Sa+=C[r]*pow(a,r)*pow(1-a, N-1-r);
        Sb+=C[r]*pow(b,r)*pow(1-b, N-1-r);
    }
    return 1-Sa*Sb;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cout<<solve();
}