취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1344번 문제인 축구이다.
문제는 아래 링크를 확인하자.

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

어떤 한 팀이 5분에 골을 넣을 확률을 $p_1$, 넣지 못할 확률을 $p_2$, 경기시각 $5t$에 그 팀이 얻은 점수가 n일 확률을 $dp[t][n]$라 할 때 $dp[t][n]=dp[t-1][n-1]\ast p_1+dp[t-1][n]\ast p_2$의 관계가 성립함을 관찰하자. (단, $t>0$, $n>0$)

위의 점화식을 이용해 각 팀의 점수가 소수일 확률을 구하고, 이를 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long double ld;

ld dp1[19][19];
ld dp2[19][19];
ld p1, p2;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	dp1[0][0] = 1;
	cin >> p1; p1 /= 100;
	p2 = 1 - p1;

	for (int t = 1; t < 19; t++) {
		dp1[t][0] = dp1[t - 1][0] * p2;
		for (int n = 1; n <= t; n++) {
			dp1[t][n] = dp1[t - 1][n - 1] * p1 + dp1[t - 1][n] * p2;
		}
	}

	dp2[0][0] = 1;
	cin >> p1; p1 /= 100;
	p2 = 1 - p1;

	for (int t = 1; t < 19; t++) {
		dp2[t][0] = dp2[t - 1][0] * p2;
		for (int n = 1; n <= t; n++) {
			dp2[t][n] = dp2[t - 1][n - 1] * p1 + dp2[t - 1][n] * p2;
		}
	}

	p1 = dp1[18][2] + dp1[18][3] + dp1[18][5] + dp1[18][7] + dp1[18][11] + dp1[18][13] + dp1[18][17];
	p2 = dp2[18][2] + dp2[18][3] + dp2[18][5] + dp2[18][7] + dp2[18][11] + dp2[18][13] + dp2[18][17];

	cout << fixed;
	cout.precision(10);

	cout << 1 - (1 - p1) * (1 - p2);
}