두 팀중 적어도 한 팀이 소수만큼 점수를 얻을 확률

1344번: 축구

 

90분간 이루어지는 축구 경기를 5분 간격으로 나눈다.

 

처음 간격은 처음 5분, 두번째 간격은 그 다음 5분...

 

각 간격에서 A,B팀이 각각 득점할 확률이 주어진다

 

각 간격에서 A,B팀은 각각 많아야 한골씩 득점할 수 있다

 

경기가 끝났을 때 적어도 한 팀이 소수로 득점할 확률은?

 

------------------------------------------------------------------------------------------------------------------------------------

 

5분씩 간격이 나눠지고 전체 경기 시간은 90분이므로 총 18간격씩 이루어진다

 

각 간격에서 두 팀은 독립적으로 최대 1골씩 넣을 수 있다

 

dp[i][a][b] = i번째 간격에서 A팀이 a득점, B팀이 b득점할 확률

 

각 간격에서 A팀의 득점확률은 pa, B팀의 득점확률은 pb

 

dp[1][0][0] = (1-pa)(1-pb)

 

dp[1][0][1] = (1-pa)pb

 

dp[1][1][0] = pa(1-pb)

 

dp[1][1][1] = papb

 

그러면 i번째 간격에서 가능한 경우는 (A팀 득점, B팀 득점), (A팀 득점, B팀 노득점)

 

(A팀 노득점, B팀 득점), (A팀 노득점, B팀 노득점)

 

dp[i][a][b] = dp[i-1][a-1][b-1]*papb + dp[i-1][a][b-1]*(1-pa)pb + dp[i-1][a-1][b]*pa(1-pb) + dp[i-1][a][b]*(1-pa)(1-pb)

 

이렇게 쓰면 a >= 1, b >= 1에 따라 나눠줘야해서 불편하니까

 

dp[i-1][a][b]를 기준으로 A가 득점하면 dp[i][a+1][b]에 더해주고

 

B가 득점하면 dp[i][a][b+1]에 더해주고

 

A,B가 득점하면 dp[i][a+1][b+1]에 더해주고

 

A,B가 둘다 득점 못하면 dp[i][a][b]에 더해주는게 간단할듯 

 

입력이 퍼센트로 들어오기 때문에 단위를 바꿔주고

 

a = int(input())/100
b = int(input())/100

dp = [[[0]*19 for _ in range(19)] for _ in range(19)]

dp[1][1][0] = a*(1.0-b)
dp[1][1][1] = a*b
dp[1][0][1] = (1.0-a)*b
dp[1][0][0] = (1.0-a)*(1.0-b)

for i in range(2,19):

    for x in range(i):
        
        for y in range(i):
        
            dp[i][x][y] += dp[i-1][x][y]*(1.0-a)*(1.0-b)
            dp[i][x+1][y] += dp[i-1][x][y]*a*(1.0-b)
            dp[i][x][y+1] += dp[i-1][x][y]*(1.0-a)*b
            dp[i][x+1][y+1] += dp[i-1][x][y]*a*b

prime = [2,3,5,7,11,13,17]

p = 0.0

for i in range(19):
    
    for j in range(19):
        
        if (i in prime) or (j in prime):

            p += dp[18][i][j]

print(p)

 

 

마지막에 정답을 찾을 때는?

 

적어도 한 팀이 소수를 득점해야하니까 dp[18][i][j]에서 i나 j가 소수인 경우면 더해주면 된다

 

이는 if (i in prime) or (j in prime):으로 간단하게 가능

 

여기서 이상하게 생각해서 꼬여버린