백준 1344번: 축구

https://www.acmicpc.net/problem/1344

 

두 팀의 골을 넣을 확률이 주어질 때, 90분 동안 5분 간격으로 시도할 때 두 팀 중 하나라도 소수 개의 골을 넣을 확률을 구하는 문제이다. 역으로 전부 소수 개가 아닌 경우의 확률을 구하여 1에 빼주면 구해야 하는 확률을 구할 수 있다.

 

우선, 90분동안 5분 간격이므로 시도 횟수는 18회가 되므로 소수가 시도 횟수와 아닌 0에서 18까지의 수를 미리 저장한다.

final static int TOTAL_TRY = 18;
final static int[] NOT_PRIME_NUMBER = {0, 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18};

 

 

각 확률을 입력을 받은 후, 성공 확률이 전부 100 혹은 전부 0인 경우 시도를 몇번 하더라도 소수 개의 골을 넣을 수 없으므로 미리 출력한다.

if (aPercent == 1.0 && bPercent == 1.0) {
    System.out.print(0.0);
    return;
}
if (aPercent == 0.0 && bPercent == 0.0) {
    System.out.print(0.0);
    return;
}

 

 

소수가 아닐 확률은 두 팀 모두 소수가 아닌 골을 넣는 확률이다. 각각의 팀이 단순한 소수가 아닌 골을 넣을 확률을 구한 후, 이항계수를 계산해주어야 한다. 18개의 시도에서 갯수개 만큼만 성공하기 때문에 이항계수를 구해서 곱해주어야 한다. 구한 후, 두 확률을 곱한 것이 각각의 두 팀이 해당 소수가 아닌 골을 넣은 확률이 되며 이를 최종 확률에 더해준다. (1 - 최종확률)이 최종 결과이다.

double notPrimePercent = 0.0;
for (int firstNumber : NOT_PRIME_NUMBER) {
    double firstPercent = 1;
    for (int i = 0; i < firstNumber; i++) {
        firstPercent *= aPercent;
    }
    for (int i = 0; i < TOTAL_TRY - firstNumber; i++) {
        firstPercent *= (1 - aPercent);
    }
    firstPercent *= combination(firstNumber);
    for (int secondNumber : NOT_PRIME_NUMBER) {
        double secondPercent = 1;
        for (int i = 0; i < secondNumber; i++) {
            secondPercent *= bPercent;
        }
        for (int i = 0; i < TOTAL_TRY - secondNumber; i++) {
            secondPercent *= (1 - bPercent);
        }
        secondPercent *= combination(secondNumber);
        notPrimePercent += (firstPercent * secondPercent);
    }
}
System.out.print((1 - notPrimePercent));

private static long combination(int k) {
    long result = 1;
    for (int i = 0; i < k; i++) {
        result *= (TOTAL_TRY - i);
        result /= (i + 1);
    }
    return result;
}

 

 

결과 코드는 다음과 같다.

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

public class 축구1344 {
    
    final static int TOTAL_TRY = 18;
    final static int[] NOT_PRIME_NUMBER = {0, 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        double aPercent = Double.parseDouble(br.readLine()) / 100;
        double bPercent = Double.parseDouble(br.readLine()) / 100;
        br.close();
        
        if (aPercent == 1.0 && bPercent == 1.0) {
            System.out.print(0.0);
            return;
        }
        if (aPercent == 0.0 && bPercent == 0.0) {
            System.out.print(0.0);
            return;
        }
        double notPrimePercent = 0.0;
        for (int firstNumber : NOT_PRIME_NUMBER) {
            double firstPercent = 1;
            for (int i = 0; i < firstNumber; i++) {
                firstPercent *= aPercent;
            }
            for (int i = 0; i < TOTAL_TRY - firstNumber; i++) {
                firstPercent *= (1 - aPercent);
            }
            firstPercent *= combination(firstNumber);
            for (int secondNumber : NOT_PRIME_NUMBER) {
                double secondPercent = 1;
                for (int i = 0; i < secondNumber; i++) {
                    secondPercent *= bPercent;
                }
                for (int i = 0; i < TOTAL_TRY - secondNumber; i++) {
                    secondPercent *= (1 - bPercent);
                }
                secondPercent *= combination(secondNumber);
                notPrimePercent += (firstPercent * secondPercent);
            }
        }
        System.out.print((1 - notPrimePercent));
    }
    
    private static long combination(int k) {
        long result = 1;
        for (int i = 0; i < k; i++) {
            result *= (TOTAL_TRY - i);
            result /= (i + 1);
        }
        return result;
    }
}