[SWEA] 소수 완제품 확률

삼성 SW 아카데미 1266번 소수 완제품 확률

확률과 통계에 대한 기본 개념이 있어야 풀 수 있는 문제였던 것 같다

 

두 가구 장인이 만든 완제품의 수가 최소 한 명이라도 소수일 확률은 1 - 둘다 소수가 아닐 확률이라는 점을 먼저 생각해보았다

A,B는 독립시행이므로 둘다 소수가 아닐 확률은 A가 소수가 아닐 확률 * B가 소수가 아닐 확률이다

 

장인이 만든 완제품이 소수가 아닐 확률을 구하기 위해서 not prime 배열을 선언해 18이하의 소수가 아닌 수들을 모아보았다

완제품을 만들 수 있는 확률이 p일 때 18개중  n개의 완제품을 만들기 위해서는 $ C(n,r) \times (p^n) \times ((1-p)^(18-n)) $을 계산해주면 된다

combination 값을 몇개만 쓰기때문에 매번 구하는 것보다 미리 저장해놓는 것이 좋을 것 같다 배열로 저장해주었다

각각 계산 후 곱하여 1에서 빼주면 정답

 

#include <stdio.h>
#include <cmath>
 
int not_prime[] = {0,1,4,6,8,9,10,12,14,15,16,18};
int comb[] = {1,18,3060,18564,43758,48620,43758,18564,3060,816,153,1};
 
double get_percent(int valid_percent, int valid_count){
    double res = 1,p = (double)valid_percent/100.0;
    //printf("%lf\n",p);
    for(int i = 0 ; i < valid_count ; i++){
        res *= p;
    }
    for(int i = valid_count ; i < 18 ; i++){
        res *= (1.0-p);
    }
    return res;
}
 
int main(){
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d",&T);
    for(int test_case = 1 ; test_case <= T ; test_case++){
        int A,B;
        scanf("%d %d",&A,&B);
 
        // 최소 한명이라도 소수 == 1 - 둘다 소수가 아닌거
        double a = 0.0,b=0.0;
 
        // a가 소수가 아닐 확률
        for(int i = 0 ; i < 12; i++){
            double r = get_percent(A,not_prime[i]);
            r *= comb[i];
            a += r;
        }
 
        // b가 소수가 아닐 확률
        for(int i = 0 ; i < 12; i++){
            double r = get_percent(B,not_prime[i]);
            r *= comb[i];
            b += r;
        }
 
        printf("#%d %lf\n",test_case,1-a*b);
    }
}