[Algorithm]Baekjoon 1344번 :: 축구

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

 

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
 
using namespace std;
 
 
int combination(int n, int r) 
{
    if (r > n) return 0;
    if (r == 0 || r == n) return 1;
 
    // nCr = n! / (r! * (n-r)!)
    int result = 1;
    for (int i = 1; i <= r; i++) {
        result *= (n - i + 1);
        result /= i;
    }
    return result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
 
    double a, b;
    cin >> a >> b;
 
    a /= 100;
    b /= 100;
 
    int noPrimeNums[12] = {0,1,4,6,8,9,10,12,14,15,16,18 };
 
    double aSum = 0;
    double bSum = 0;
 
    for (int i = 0; i < 12; ++i)
    {
        int r = noPrimeNums[i]; // 넣어야 할 골 개수.
 
        double aGoalRatio = pow(a, r);
        double aNoGoalRatio = pow(1 - a, 18 - r);
 
        double bGoalRatio = pow(b, r);
        double bNoGoalRatio = pow(1 - b, 18 - r);
 
        double combi = combination(18, r);
 
        aSum += aGoalRatio * aNoGoalRatio * combi;
        bSum += bGoalRatio * bNoGoalRatio * combi;
    }
 
    cout << 1 - (aSum * bSum);
}
 
 

 

 

간만에 푸는 조합문제.

사실 정확히는 조합쪽으로 생각의 흐름을 잘 유도해야하는 문제이다.

 

문제에선 한 경기 90분이 주어지고, 그걸 5분가격으로 18개의 구간으로 나눈다.

각 구간마다 A팀과 B팀이 골을 넣을 확률이 주어진다.

 

18구간 각각 따로따로 확률이 주어진다는게 아니니 헷갈리지 말것. 

인풋값으로 30,50이 주어지면 A팀은 30%, B팀은 50%확률로 각 구간마다 골을 넣을 수 있다.

 

여기서 만약 '최종적'으로 A팀이 1골만 득점한 '모든 경우의 수'를 구한다면,

pow(0.3, 1) * pow(0.7, 17) * 18이 될 것이다.

 

대충 생각하면 뒤에 18을 왜곱했는지 이해가 안될텐데,  '모든 경우의 수'를 구해야 한다고 했다.

즉, 한골을 첫구간에 넣었을 수도 있고, 두번째 구간에 넣었을 수도 있고.. 마지막 18번째 구간에 넣었을 수도 있기 때문이다.

 

예를들어 18개의 구간이 아니라 생각하기 쉽게 3경기라 하자.

그러면 최종적으로 한골만 득점한 경우는 아래와 같다.

1 0 0

0 1 0

0 0 1

 

그러면 3개의 구간인데, 두골을 득점한 경우는?

 

1 1 0

1 0 1

0 1 1

 

이쯤 되면 알수있는데, nCr 형태의 조합(Combination)이다.

총 n개의 구간이 있고, r개의 득점을 하는 경우를 구하기 위해 nCr을 사용한다.

nCr 코드는 알아서...구현하면 된다.

 

 

자 문제에서는 '적어도' 한 팀이 소수개수의 골을 득점할 확률을 구하라 했다.

적어도 한팀이라 했으니, A팀만 소수개수거나 B팀만 소수개수거나, 아니면 두 팀다 소수개수인 경우가 해당된다.

이 말은, 다시 바꾸면 '1 - (두 팀 다 소수개수의 골을 득점하지 않을 확률)' 이 된다.

 

그러면 두 팀 다 소수개수의 골을 득점하지 않을 확률은?

(A팀이 소수개수 골 득점하지않을 확률) * (B팀이 소수개수 골 득점하지 않을 확률)

 

그러면 A팀이 소수개수 골 득점하지 않을 확률은?

최종적으로 소수개수가 아닌 골들의 확률을 누적시켜주면 된다.

소수개수가 골로는 0,1,4,6,8,9,10,12,14,15,16,18    총 12개가 있다.

여기서 0을 빼먹으면 안된다. 0골 또한 소수가 아니니까.

 

처음 예시로, A팀 구간골 확률이 30%이고 최종적으로 4골의 형태를 이뤄야한다고 가정하자.

그러면 아래와 같이 된다.

 

pow(0.3, 4) * pow(0.7, 18 - 4 == 14)  *  18C4

 

이런식으로 0 ,1,4 .... 18까지 전부 누적시키면 이 누적값은 마침내 구하려고 했던 '소수개수가 아닌 골을 넣을 확률' 이 된다.

 

B도 똑같이 구한다음,  두 갑을 곱하고 1에서 이 값을 빼낸 확률이 문제에서 요구하는 값이 된다.