1266. [S/W 문제해결 응용] 9일차 - 소수 완제품 확률

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

핵심 => DP로 이항계수 구하기 DFS로 구하면 너무 많음.

DP로 1부터 n까지 i,i이랑 i,0은 1로 설정하고

2부터 n까지 진행하는데, j는 1부터 i까지 (0은 이미 1로 만들었으므로,, ) 

이렇게 이항계수를 구해놓으면 확률을 구하면 된다. A,B의 각각 성공확률 실패확률에 소수는 7가지로 정해져있으므로

7가지 케이스에 대한 이항계수를 곱한 합을 구한 뒤에 

이것은 A,B가 각각 소수를 만들 확률인데 한사람이라도 소수를 만들 확률이 필요하니까

전체에서 둘다 소수를 안만들 확률을 빼면 됨.

 

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
int N;
int Combi[19][19];
int prime[7] = { 2,3,5,7,11,13,17 };

void init()
{
	for (int i = 1; i <= 18; i++)
	{
		Combi[i][i] = 1;
		Combi[i][0] = 1;
	}
	for (int i = 2; i <= 18; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			Combi[i][j] = Combi[i - 1][j] + Combi[i - 1][j - 1];
		}
	}
}

double Cal(double r, int n)
{
	double real = 1.0;
	for (int i = 0; i < n; i++)
	{
		real *= r;
	}
	return real;
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		init();
		double skillA, skillB;
		cin >> skillA >> skillB;

		skillA /= 100.0;
		skillB /= 100.0;


		double A = 0.0;
		double B = 0.0;
		for (int i = 0; i < 7; i++)
		{
			A += Combi[18][prime[i]] * Cal(skillA, prime[i]) * Cal(1-skillA, 18 - prime[i]);
			B += Combi[18][prime[i]] * Cal(skillB, prime[i]) * Cal(1-skillB, 18 - prime[i]);
		}
		double answer = 1 - (1 - A) * (1 - B);
		printf("#%d %.6f\n", test_case, answer);
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}