본문 바로가기
알고리즘 문제/SWEA

[SWEA - Java] 1266. 소수 완제품 확률

by 건복치 2021. 10. 27.
반응형

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18Sx36IwACFAZN 

설명

주어진 시간은 90분이며, 각 가구 장인은 5분 안에 최대 1개의 완제품을 만들 수 있다고 가정

 

5분에 성공하면 최대 1개 / 실패하면 0개

  • 90분간 모두 성공하면 → 18개
  • 90분간 모두 실패하면 → 0개

 

5분 10분 15분



...




    90분
1 2 3 16 17 18
Fail : 0
or
Success : 1
         

18개 중 소수는 2, 3, 5, 7, 11, 13, 17

→ 2개, 3개, ... , 17개 해당 소수 개의 개수만큼 완제품이 나올 확률을 다 더한 값

 장인이 만든 완제품의 수가 소수일 확률

 

 

A장인, B장인 두 명이니까

A장인이 만든 완제품의 수가 소수일 확률 + B장인이 만든 완제품의 수가 소수일 확률 = 정답

 

A장인을 예로 들어보자(B도 똑같은 방식으로 구하면 됨)

skillOfMasterA = A장인이 5분 안에 완제품을 만들 확률 = 80

skillOfMasterA = 100/80 = 5/4

성공할 확률 5/4 - 실패할 확률 5/1

 

A장인이 소수 2, 2개의 완제품을 만들 확률?

18C2 * (5/4)^2 * (5/1)^16 = 18개 중 2개 만큼만 완제품으로 만들 확률

 

  • 18C2 : 18개 중 소수2, 2개만큼을 뽑는 경우의 수 
  • (5/4)^2 : 각 경우에서 2개 만드는데 성공할 확률
  • (5/1)^16 : 각 경우에서 2개 만드는데 실패할 확률(18-2=16)

18개중 소수 N만큼 뽑는 경우의 수  * 각 경우에서 N개 만드는 데 성공할 확률 * 각 경우에서 N개 만드는데 실패할 확률

 

 

2개 만큼 완제품으로 만들 확률 + 3개 확률 + 5개 확률 +... + 17개 확률 = A가 소수개 완제품을 만들 확률

 

→ 2, 3, 5, 7, 11, 13, 17에서의 완제품 만들 확률을 다 뽑고 이를 합하면 됨

ex)

18C2 * (5/4)^2 * (5/1)^16

+

18C3 * (5/4)^3 * (5/1)^15

+

18C5 * (5/4)^5 * (5/1)^13

+

...

+

18C17 * (5/4)^17 * (5/1)^1

 

문제에서 요구하는 완제품이 최소 한 명이라도 소수일 확률?

1 - (1-A) * (1-B) = A, B장인에게서 소수 개 완제품이 하나라도 나올 확률 =  완제품이 최소 한 명이라도 소수일 확률

 

  • (1-A) : 전체 확률 - A장인이 소수 개 완제품을 만들 확률 = A장인이 완제품을 단 하나라도 소수 개수로 만들지 못할 확률
  • (1-B) : 위와 마찬가지
  • (1-A) * (1-B) : A, B 장인에게서 소수가 한 번도 나오지 않을 확률

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
	static int[] primeNumbers = {2, 3, 5, 7, 11, 13, 17};

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());

		for(int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());

			// 5분 안에 완제품을 만들 확률
			double skillA = Double.parseDouble(st.nextToken()) / 100;
			double skillB = Double.parseDouble(st.nextToken()) / 100;

			double A = 0, B = 0;

			for(int i = 0; i < primeNumbers.length; i++) {
				// 18개중 소수 N만큼 뽑는 경우의 수  * 각 경우에서 N개 만드는데 성공할 확률 * 각 경우에서 N개 만드는데 실패할 확률
				A += combination(18, primeNumbers[i]) * Math.pow(skillA, primeNumbers[i]) * Math.pow(1-skillA, 18-primeNumbers[i]);
				B += combination(18, primeNumbers[i]) * Math.pow(skillB, primeNumbers[i]) * Math.pow(1-skillB, 18-primeNumbers[i]);
			}
			
			//double result = 1 - (1 - A) * (1 - B);
			double result =  A + B - (A * B);

			sb.append("#" + test_case + " " + String.format("%.6f", result) + "\n");			
		}

		System.out.println(sb.toString());
	}

	// 조합의 수 구하기 - nCr
	public static int combination(int n, int r) {
		if(n == r || r == 0) 
			return 1; 
		else 
			return combination(n - 1, r - 1) + combination(n - 1, r); 
	}

}
반응형

댓글