[swexpert] 1266. 소수 완제품 확률 (C++, 조합)

일단 1~18 사이 소수를 먼저 구해준 후 A가 소수 개를 성공할 확률, B가 소수 개를 성공할 확률을 구한다.

 

만약 A가 2개를 성공한다고 칠 때 18개의 구간 중 어느 구간 2개에서 성공하는 지를 구해줘야 하므로

18C2를 구해서 a의 2개 성공확률에 곱해줘야 된다.

 

둘 중 적어도 하나가 소수인 확률은 전체확률인 1에서 둘다 소수가 아닌 확률(여집합)을 빼주면 된다.

 

교집합을 구하는 방법과 소수개를 성공할 확률을 구하는 것까지는 잘 했는데 조합을 구해줘야 된다는 것을

떠올리지 못해 못 풀어서 해당 부분은 참고해서 했다.

조합은 nCr=n-1Cr-1 +n-1Cr의 식을 참고하여 이중배열로 미리 구해준다.

 

#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int t;
double a, b;
bool prime[39];
double res;
int comb[19][19];


void getComb() {// 18중 n개를 뽑을 조합을 구해줘야된다
	for (int i = 1; i <= 18; i++) {
		comb[i][0] = 1;
		comb[i][i] = 1;
	}

	for (int i = 2; i <= 18; i++) {
		for (int j = 1; j < i; j++) {
			comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
		}
	}


}

void PrimeCheck() {
	fill(prime, prime+19, true);
	prime[0] = false;
	prime[1] = false;
	//2부터 18까지 수들 중 소수 판별
	for (int i = 2; i <= 18; i++) {
		for (int j = 2; j*j <= i; j++) {
			if (i%j == 0) {
				prime[i] = false;
				break;
			}
		}
	}
}

double getPercent(double percent, int num) {
	double ans = 1;
	for (int i = 0; i < num; i++) {
		ans *= percent/100; //완제품 성공률
	}
	for (int i = 0; i < 18 - num; i++) {
		ans *= (100 - percent)/100;
	}

	return ans;
}

void getResult() {
	double suma = 0, sumb = 0;
	double ans = 0, ans2 = 0;
	for (int i = 0; i <= 18; i++) {
		if (!prime[i]) {// 소수라면
			suma = getPercent(a, i);//i개 성공확률
			ans = ans + comb[18][i] * suma;
			sumb = getPercent(b, i);
			ans2 = ans2 + comb[18][i] * sumb;

		}
	}
	
	//전체 확률에서 두개 모두 소수가 아닐 확률을 빼주면 된다.
	// 그럼 적어도 둘 중 하나는 소수겠지. (합집합부분)
	res = 1 -  ans*ans2;
}




int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed;
	cout.precision(6);

	PrimeCheck();
	getComb();
	cin >> t;
	for (int tc = 1; tc <= t; tc++)
	{
		cin >> a >> b;
		res = 0;
		getResult();

	
		cout << "#" << tc <<" "<< res<<"\n";
	}


	return 0;
}