1344 축구

문제 정의

축구 팀 A와 B가 90분에 걸쳐 경기를 한다. 적어도 한 팀이 골을 소수로 득점할 확률을 구하라.

경기를 5분 간격으로 나누고, 처음 간격은 처음 5분이다.

A팀과 B팀이 이 간격에서 득점할 확률이 주어질 때, 경기가 끝난 후 적어도 한 팀이 골을 소수로 득점할 확률을 구하시오.

입력 예) 50 50

---

문제 풀이

이 문제는 DP로 풀 수 있습니다.

DP[p][a][b] : p번째 간격이 지났을 때, A팀이 a골, B팀이 b골을 넣었을 확률

즉, pa를 A가 넣을 확률, pb를 B가 넣을 확률이라고 할 때,

DP[p][a][b] = DP[p-1][a][b] * (1.0 - pa) * (1.0 - pb) +

DP[p-1][a-1][b] * pa * (1.0 - pb) +

DP[p-1][a][b-1] * (1.0-pa) * pb +

DP[p-1][a-1][b-1] * pa * pb

로 구할 수 있습니다.

---

소스코드

#include< stdio.h >
double dp[20][20][20];
int prime[7] = { 2,3,5,7,11,13,17 };
int isprime(int x) {
	for (int i = 0; i < 7; i++)
		if (x == prime[i])
			return 1;
	return 0;
}
int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	
	double A = a / 100.0, B = b / 100.0;
	dp[1][0][0] = (1. - A) * (1. - B);
	dp[1][1][0] = A * (1. - B);
	dp[1][0][1] = (1. - A) * B;
	dp[1][1][1] = A*B;
	
	for (int p = 2; p <= 18; p++) {
		for (a = 0; a <= 18; a++) {
			for (b = 0; b <= 18; b++) {
				dp[p][a][b] = dp[p - 1][a][b] * (1. - A)*(1. - B);
				if (a != 0)
					dp[p][a][b] += dp[p - 1][a - 1][b] * A * (1. - B);
				if (b != 0)
					dp[p][a][b] += dp[p - 1][a][b - 1] * (1. - A) * B;
				if (a != 0 && b != 0)
					dp[p][a][b] += dp[p - 1][a - 1][b - 1] * A * B;
			}
		}
	}	
	double ans = .0;
	for(a=0;a<=18;a++){
		for (b = 0; b <= 18;b++) {
			if (isprime(a) || isprime(b))
				ans += dp[18][a][b];
		}		
	}
	printf("%.10lf\n", ans);
	return 0;
}