시리즈 우승 확률 계산

A팀과 B팀이 총 N경기인 시리즈 결승에 올랐다.
N/2+1 경기를 먼저 이기는 팀이 우승을 하게 된다.
A가 한 경기를 이길 확률은 p이고 비길 경우는 없다고 가정한다.
A가 시리즈을 우승 하기 위해 i 게임을 더 이겨야 하고 B가 우승 하기 위해서는 j 게임 더 이겨야 한다고 했을때 DP(i, j)를 A가 우승할 확률이라고 하자.

DP에 대한 점화식은 다음과 같다.
DP(0, j) = 1
DP(i, 0) = 0
DP(i, j) = p * DP(i-1, j) + (1-p) * DP(i, j-1) (i, j >= 1)

A가 우승할 확률을 계산하는 프로그램을 자바 코드로 나타내면 다음과 같다.


public class Main
{
    public static void func(int n, float p, int i, int j)
    {
        // n경기
        // a팀 이길 확률 p
        // 우승까지 남은 승수 a:i경기, b:j경기
        // DP(i, j) = p * DP(i-1, j) + q * DP(i, j-1)
        float q = 1 - p; // b가 이길 확률
        float[][] DP = new float[n/2+2][n/2+2]; // n의 과반수 경기 이기면 우승
        
        for (int k=1; k<=n/2+1; k++)
        {
            DP[0][k] = 1;
            DP[k][0] = 0;
        }
        for (int k=1; k<=n/2+1; k++)
        {
            for (int l=1; l<=n/2+1; l++)
                DP[k][l] = p * DP[k-1][l] + q * DP[k][l-1];
        }
        
        for (int k=0; k<=n/2+1; k++)
        {
            for (int l=0; l<=n/2+1; l++)
                System.out.print(arr[k][l] + " ");
            System.out.println();
        }
    
	public static void main(String[] args) 
	{
		func(7, 0.4f, 4, 4); // 마지막 값이 결과
	}
}

좋은 웹페이지 즐겨찾기