[백준 1344] 축구(Java)

문제 링크 : https://www.acmicpc.net/problem/1344

이 문제는 DP를 이용하여 풀 수 있습니다. 점화식을 생성하기 위해선 규칙을 잘 파악해야 합니다.

총 구간은 18개의 구간으로 진행되며, 각각의 구간은 아래의 4가지 경우의 수가 존재합니다.

1. A팀이 득점하고 B팀이 득점했을 경우
2. A팀이 득점하고 B팀이 득점하지 않았을 경우
3. A팀이 득점하지 않았고 B팀이 득점했을 경우
4. A팀이 득점하지 않았고 B팀이 득점하지 않았을 경우

즉 아래의 4가지의 케이스에 따라, 1번 케이스는 두 팀의 득점 카운트를 1 올리고, 2,3번 케이스는 각각 득점한 팀의 카운트만 1 올리고, 4번 케이스는 두 팀의 득점 카운트를 모두 올리지 않습니다. 따라서 점화식은 아래와 같이 설정할 수 있습니다.

DP[i][j][k] : i번 구간에서 A팀이 j골을 넣었고 B팀이 k골을 넣었을 확률

위의 점화식을 기준으로 i를 증가시키면서 4개의 케이스에 따른 경우를 계속 추가해줍니다. 한 팀이 득점했을 경우 그 팀의 득점 확률을 곱해주며, 득점하지 못했을 경우 (1-득점 확률)을 곱하여 계산합니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

class Main{
    static int DIFF_NUM = 90/5;
    static double[][][] dp = new double[DIFF_NUM+1][DIFF_NUM+1][DIFF_NUM+1];

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        double A = Double.parseDouble(br.readLine())/100;
        double B = Double.parseDouble(br.readLine())/100;
        setDp(A,B);

        double res = 0;
        for(int i=0;i<=DIFF_NUM;i++){
            for(int j=0;j<=DIFF_NUM;j++){
                if(isPrimeNum(i) || isPrimeNum(j)) res += dp[DIFF_NUM][i][j];
            }
        }

        System.out.printf("%.7f", res);
    }

    private static void setDp(double A, double B){
        dp[0][0][0] = 1.0;
        for(int i=1;i<=DIFF_NUM;i++){
            for(int j=0;j<=i;j++){
                for(int k=0;k<=i;k++){
                    if(j>0) dp[i][j][k] += dp[i-1][j-1][k] * A * (1-B);
                    if(k>0) dp[i][j][k] += dp[i-1][j][k-1] * (1-A) * B;
                    if(j>0 && k>0) dp[i][j][k] += dp[i-1][j-1][k-1] * A * B;
                    dp[i][j][k] += dp[i-1][j][k] * (1-A) * (1-B);
                }
            }
        }
    }

    private static boolean isPrimeNum(int n){
        if(n < 2) return false;
        for(int i=2; i*i<=n; i++) if(n%i==0) return false;
        return true;
    }
}