[BOJ-1344] 축구

ParkJunHa·2023년 8월 29일

다이나믹 프로그래밍 수학 조합론 확률론

BOJ

목록 보기

15/85

[Gold IV] 축구 - 1344

문제 링크

성능 요약

메모리: 31256 KB, 시간: 40 ms

분류

조합론, 다이나믹 프로그래밍, 수학, 확률론

문제 설명

홍준이는 축구 경기를 보고 있다. 그러다가 홍준이는 역시 두 팀 중 적어도 한 팀이 골을 소수로 득점할 확률이 궁금해 졌다. 축구 경기는 90분동안 이루어지고, 분석을 쉽게하기 위해서 경기를 5분 간격으로 나눴다. 처음 간격은 처음 5분이고, 두 번째 간격은 그 다음 5분, 그리고 이런식으로 나눈다. 경기가 진행되는 동안 각 간격에서 A팀이 득점할 확률과 B팀이 득점할 확률이 주어진다. 그리고, 각 간격에서 두 팀은 각각 많아야 한 골을 득점할 수 있다. 경기가 끝난 후 적어도 한 팀이 골을 소수로 득점할 확률을 구하시오.

입력

첫째 줄에 A팀이 득점할 확률, 둘째 줄에 B팀이 득점할 확률이 퍼센트 단위로 주어진다. 퍼센트 단위로 주어지는 확률은 모두 0보다 크거나 같고 100보다 작거나 같은 정수이다.

출력

첫째 줄에 적어도 한 팀이 골을 소수로 득점할 확률을 출력한다. 정답과의 절대/상대 오차가 10-6이내인 경우에 정답이다.

풀이

아이디어

문제의 조건이 2개이다.
승률을 만족할 때, 그 점수가 소수(Prime number)일 확률을 구하는 문제이다.

우선 까맣게 잊고 있던 이항계수에 대한 내용을 다시 한 번 정리해본다.

이항계수는 주어진 크기 집합에서 원하는 개수만큼 순서 없이 뽑는 조합의 가짓수를 일컫는다. 이항계수는 선택하거나 하지 않거나 두가지 선택만 있다.

\binom{n}{k} = nCk = \frac{n!}{(n-k)!k!}

이항 계수의 성질로는 다음과 같다.

\binom{n}{k} = \binom{n}{n-k}

n개 중 k를 선택하는 것은 n개 중 선택받지 못한 나머지를 선택하는 확률과 같다.

\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}

이항계수 정의식을 잘 조물조물하면 유도할 수 있다.

\sum_{k=0}^n \binom{n}{k} = 2^n

파스칼의 삼각형이다, 이를 이용한 이항정리는 아래와 같다.

(a+b)^n = \sum_{k=0}^n \binom{n}{k}a^{n-k}b^k

이를 기반으로 문제에 해당하는 식을 세워보자.
시간을 5분단위로 쪼갰으므로, 총 경기 90분에서 나올 수 있는 확률은 18개의 파트로 나눌 수 있다.

따라서 총 낼 수 있는 점수는 18점이 최대이고, 18 이햐의 소수는 다음 집합이다.

S = \{2, 3, 5, 7, 11, 13, 17\}

둘 중 하나라도 이 집합안에 있는 점수를 낸다면 확률상 참이므로, 반대로 생각해 둘다 소수인 점수를 내지 못하는 경우로 문제를 풀이하면 조금 더 수식을 간단히 할 수 있다.

$P$ 를 둘다 소수인 점수를 내지 못하는 확률 이라고 정의하면 아래 수식을 따른다.

P(k) = \sum_{k=0}^{18} \binom{18}{k}a^{18-k}(1-a)^k \,|k \notin S

이때 $a$ 가 못넣을 확률과 $b$ 가 못 넣을 확률을 1에서 빼주면 된다.
이를 수식으로 정리하면 다음과 같이 나온다.

1 - P_a(k) \times P_b(k)

둘을 곱하는 이유는 두 확률이 독립이기 때문.

이 수식을 그냥 구현하기만 하면 될 듯 하다. 이때 binom을 구하는 부분에 DP를 적용해준다면 시간복잡도상 효율을 가져올 수 있다.

코드

PART = 18
pa = int(input())*0.01
pb = int(input())*0.01

nprime = [0, 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18]

dp = [[0] * (PART+1) for _ in range(PART+1)]

def binom(n, m):
    if n == m or m == 0:
        return 1
    
    if m >= n:
        return 0
    
    if dp[n][m] != 0:
        return dp[n][m]
    else:
        dp[n][m] = binom(n-1, m) + binom(n-1, m-1)
        return dp[n][m]

res = 0
aa, bb = 0, 0
for r in nprime:
    aa += binom(18, r) * (pa**r) *  ((1-pa)**(PART - r))
    bb += binom(18, r) * (pb**r) *  ((1-pb)**(PART - r))

print(1-aa*bb)

회고

수학 공부좀 하자..

ParkJunHa

PS린이

이전 포스트

[BOJ-13913] 숨바꼭질 4

다음 포스트