문제 정의


축구 팀 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;
}


'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 1194 달이 차오른다, 가자.  (0) 2020.08.11
BOJ 6087 레이저통신  (0) 2020.08.09
BOJ 11505 구간 곱 구하기  (0) 2020.08.06
1344 축구  (0) 2018.06.01
1351 무한 수열  (0) 2018.05.28
1670 정상 회담 2  (0) 2018.05.17

+ Recent posts