백준1344 축구

작성일 | In

문제 링크

  • http://icpc.me/1344

사용 알고리즘

  • DP

시간복잡도

  • 약 183

풀이

dp[t][a][b]를 t번째 단계에서 점수가 a:b일 확률이라고 정의를 해줍시다.
dp[t][a][b]가 만들어지는 경우는 아래 4가지입니다.

  • a만 득점 : dp[t-1][a-1][b] * pa * (1-pb)
  • b만 득점 : dp[t-1][a][b-1] * (1-pa) * pb
  • 둘 다 득점 : dp[t-1][a-1][b-1] * pa * pb
  • 둘 다 실패 : dp[t-1][a][b] * (1-pa) * (1-pb)

위 식을 이용해 dp table을 채워주시면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

double dp[20][20][20];

bool isPrime(int n){
	if(n < 2) return 0;
	for(int i=2; i*i<=n; i++) if(n%i==0) return 0;
	return 1;
}

int main(){
	double a, b; cin >> a >> b;
	dp[0][0][0] = 1.0;
	a /=100, b /= 100;
	for(int i=1; i<=18; i++){
		for(int j=0; j<=i; j++){
			for(int k=0; k<=i; k++){
				if(j > 0) dp[i][j][k] += dp[i-1][j-1][k] * a * (1-b);
				if(k > 0) dp[i][j][k] += dp[i-1][j][k-1] * (1-a) * b;
				if(j > 0 && k > 0) dp[i][j][k] += dp[i-1][j-1][k-1] * a * b;
				dp[i][j][k] += dp[i-1][j][k] * (1-a) * (1-b);
			}
		}
	}

	double ans = 0;
	for(int i=0; i<=18; i++){
		for(int j=0; j<=18; j++){
			if(isPrime(i) || isPrime(j)) ans += dp[18][i][j];
		}
	}
	printf("%.9lf", ans);
}