[백준] 35272번 - 사격 훈련

문제

<배경>

슬슬 다가오는 예비군 시즌을 의식하다보니 눈에 띄는 제목의 문제가 있어 클릭해보았다.

 

<난이도>

---

<입력>

N이 첫번째 줄에,

P, Q가 두번째 줄에 공백으로 구분되어 주어진다.

 

<출력>

기댓값의 최댓값

---

풀이

푸르매가 전부 쏘고 나서 하늘이로부터 도움을 받는 것으로 순서를 정해서 계산했다.

문제에서는 확률을 대문자로 표시했지만 이 글에서는 소문자 $p,q$를 사용했다.

 

일단 푸르매가 2차시기에 $N$번 쏴서 $n$개를 맞출 확률을 $Q(n)$이라고 하자.

이 때 값은 $_{N}\textrm{C} _n q^n (1-q)^{(N-n)}$이 된다.

 

비슷하게 하늘이가 푸르매에게 $n$회 지원을 해줬을 때 $k$개가 명중할 확률을 $P_k (n)$이라고 하자. 

이 때 값은 $_{n}\textrm{C} _k p^k (1-p)^{(n-k)}$ 이다.

 

이제 기댓값을 계산해야한다.

 

하늘이가 $n$회의 지원을 했을 때, 

0회 명중하면 기대값은 $\Sigma_{k=0}^N k Q_k P_0 (n)$이고,

1회 명중하면 기대값은 $\Sigma_{k=0}^{N-1} (k+1) Q_k P_1 (n)$이다.

이렇게 계속 계산해서 모두 더하면 하늘이가 $n$회의 지원을 했을 때 전체 기댓값이 나오게 된다.

 

그러나 우리는 하늘이가 몇번 지원을 할 때 그 기댓값이 가장 클지를 알아야하기 때문에

하늘이가 지원할 수 있는 횟수를 모두 계산해보고 그 중 최댓값을 뽑는 방식을 사용했다.

 

아래는 위 내용을 코드로 구성한 것이다.

N=int(input())
p,q=map(float,input().split())

def comb(n,k):
    if k>(n/2):
        k=n-k
    
    mul = 1
    for i in range(k):
        mul = mul * (n-i)
        mul = mul // (i+1)
    return mul

def Q(n):
    n=int(n)
    return comb(N,n) * q**n * (1-q)**(N-n)

def P(n,k):
    return comb(n,k) * p**k * (1-p)**(n-k)

def ex(n,hit):
    summ = 0
    for i in range(N-hit+1):
        summ += (i+hit) * Q(i) * P(n,hit)
    #print(f"ex {n}, {hit}: ",summ)
    return summ

def total_ex(n):
    summ = 0
    for i in range(n+1):
        summ += ex(n,i)

    return summ

anslist=[]
for i in range(N+1):
    anslist.append(total_ex(i))

print(max(anslist))