[ SWEA 1266 ] 소수 완제품 확률 (C++)

SWExpertAcademy의 소수 완제품 확률( 1266 / D6 ) 문제이다.

 

[ 문제풀이 ]

1) 먼저, 문제를 확실하게 이해하고 우리가 구하고자 하는 값이 무엇인지에 대해서 부터 알아보자.

   입력으로 2개의 값이 주어지는데, 이 2개의 값의 의미는 "장인이 5분 안에 완제품을 만들 확률" 을 의미한다.

   입력으로 80 90 이 입력된다면, 장인A가 5분 안에 완제품을 만들 확률은 80% , 장인B가 5 분안에 완제품을 만들 확률은

   90% 가 된다는 이야기이다.

   이 때, 완제품이 최소 한 명이라도 소수일 확률을 구하는 것이 문제이다.

   장인들은 90분동안 제품을 만들고, 5분 안에 하나의 제품을 만들기 때문에 총 18개의 제품을 만들 수 있다.

   즉, 각 장인들이 18개의 제품 중에서 소수 갯수 만큼만 완제품을 만들 확률을 구해야 한다.

   그럼 우리가 구현 하기에 앞서 알고 있어야 하는 값들이 무엇인지에 대해서 생각을 해보자.

   제품 18개 중에서 2개만(2는 소수) 완제품을 만들 확률에 대해서 생각을 해보자.

   1 1 0 0 0 . . . 0 이렇게 된다면 2개만 완제품으로 만든 것이다.

   0 1 1 0 0 . . . 0 이 경우 또한, 2개만 완제품으로 만든 것이다.

   0 0 1 1 0 . . . 0 이 경우 또한, 2개만 완제품으로 만든 것이다.

   즉, 우리는 18개 중에서 2개를 뽑는 경우의 수를 알고 있어야 한다는 것이다. 수학적인 식으로 써보면 18 C 2 의 값을

   구해야 한다는 것이다. 왜냐하면 ! 위의 3가지 경우를 포함해서 18개 중에서 2개를 뽑는 경우의 수는 너무나도 많다.

   하지만 그 경우마다 모든 확률을 다 계산해 주어야 할까 ??

   아니다 ! 우리는 18개 중에서 2개만 완제품으로 만들 수 있는 확률을 구한 후, 이 확률 값에다가 18개 중에서 2개를 뽑는

   경우의 수를 곱해주면 된다.

   왜 ?? 예를 들어서 18개 중에서 2개를 뽑는 경우의 수가 50가지 경우가 존재한다고 가정해보자.

   이 50가지를 하나하나 구해가면서 1번 케이스 x 18개 중에서 2개만 완제품으로 만들수 있는 확률 + 2번 케이스 x 18개

   중에서 2개만 완제품으로 만들 수 있는 확률 + 3번케이스 .... + ... + 50번케이스 x 18개 중에서 2개만......

   이 식을 18개 중에서 2개만 완제품으로 만들 수 있는 확률 x (18 개 중에서 2개를 뽑는 경우의 수) 로 정리를 한 것이다.

   따라서 우리는 18C2, 즉 18개 중에서 2개를 뽑는 경우의 수를 알고 있어야 한다는 것이다.

   그럼 2만 알면될까 ?? 2, 3, 5, 7, 11, 13, 17 에 대해서 값들을 구해야 한다. 왜 ? 어차피 제품은 18개 이기 때문에

   그 이상의 소수들은 필요가 없다.

   그럼 이 값들을 한번 구해보자. 콤비네이션 공식에 이런 공식이 있다. nCr = (n-1)C(r-1) + (n-1)Cr

   본인은 이 공식과 2중 for문을 이용해서 먼저 1 ~ 18 사이에 있는 발생 가능한 모든 조합의 경우의 수를 계산해 주었다.

   (본문 코드 함수명 : Make_Init_State() )

  

2) 위에서 조합의 경우의 수들을 계산을 했으니, 그 다음 단계로 넘어가보자.

   그럼 18개 중에서 2개를 완제품으로 만들 확률은 어떻게 될까 ???

   아마, 완제품으로 만들확률 x 완제품으로 만들확률 x 완제품으로 못만들 확률 x ... x 완제품으로 못만들 확률

   이렇게 계산이 될 것이다. 그럼 완제품으로 만들확률은 어떻게 구할까 ??

   입력으로 주어진 값이 완제품으로 만들 확률이다. 반대로 완제품으로 만들지 못할 확률은 1에서 입력으로 주어진

   값을 빼버리면 완제품으로 만들지 못할 확률이 될 것이다.

   예를 들어서 완제품으로 만들 확률이 80% 라면, 18개 중에서 2개만 완제품으로 만들 확률은

   0.8 x 0.8 x 0.2 x 0.2 x 0.2 x .... x 0.2 가 될 것이다. 이 식을 말하고 있는 것이다.

  

3) 이제 1)번 내용과 2)번 내용을 합치면 된다.

   1)번 내용에서 "18개 중 특정 소수x 개 만큼을 뽑는 경우의 수"를 계산했고, 2)번 내용에서 "18개 중 특정 소수 x개만

   완제품으로 만들 수 있는 확률" 을 계산해 주었다.

   이제 이 2개의 값을 곱해주면 ! 18개 중에서 특정 소수 x개 만큼만 완제품으로 만들 수 있는 확률을 구할 수 있는 것이다.

   위와 같은 방식으로, A장인에 대한 값, B장인에 대한 값을 계산해 주면 된다.

 

   하지만 ! 여기서 끝이 아니다. 문제에서 구해야 하는 값은 "완제품이 최소 한명이라도 소수일 확률" 을 물어봤다.

   이 말은, 수학적으로 다시 표현하면 "전체에서, 완제품을 단 한명도 소수 갯수로 만들지 못하는 확률"을 빼버리면 된다.

   즉, 위에서 구한 값들을 1에서 빼주고, 그 값들을 다시 1에서 빼줘야 하는 것이다.

   여기서 파랑색 '1'의 의미는 "완제품을 소수 갯수로 만들지 못할 확률" 을 구하기 위해서 지금껏 구해놓은

   "소수 갯수로 만들 확률"을 1에서 빼버린다는 것이다. 여기서 사용되는 '1'이다.

   결과적으로 우리는, 두 명 모두 소수 갯수로 만들지 못할 확률의 반대 확률을 구해야 하는 것이므로, 전체 1에서 빼주는

   것이다. 이 전체 '1'에 해당하는 값이 위에서 말한 빨강색 '1'이다.

 

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
using namespace std;
 
int SoSoo[] = { 2, 3, 5, 7, 11, 13, 17 };
int Comb[20][20];
int SKMA, SKMB;
double Answer;
 
void Make_Init_State()
{
    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 Input()
{
    cin >> SKMA >> SKMB;
    // SKOA = Skill of MASTER A
    // SKOB = Skill of MASTER B;
}
 
double Calculate(int Percent, int S)
{
    double R_Value = 1.0;
    double P = (double)Percent / 100.0;
    for (int i = 0; i < S; i++) R_Value = R_Value * P;
 
    return R_Value;
}
 
void Solution()
{
    double A_Percent, B_Percent;
    A_Percent = B_Percent = 0.0;
    for (int i = 0; i < 7; i++)
    {
        double A_Success = Calculate(SKMA, SoSoo[i]);
        double A_Default = Calculate(100 - SKMA, 18 -SoSoo[i]);
        double B_Success = Calculate(SKMB, SoSoo[i]);
        double B_Default = Calculate(100 - SKMB, 18 - SoSoo[i]);
 
        A_Percent = A_Percent + Comb[18][SoSoo[i]] * A_Success * A_Default;
        B_Percent = B_Percent + Comb[18][SoSoo[i]] * B_Success * B_Default;
    }
    Answer = 1 - ((1 - A_Percent) * (1 - B_Percent));
}
 
void Solve()
{
    Make_Init_State();
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout << fixed;
    cout.precision(6);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}