m면체 주사위 n개를 굴려서 나올 수 있는 경우의 수를 구하는 방법

3886번: Expected Allowance (acmicpc.net)

 

 

m면체 주사위 n개를 굴려서 나온 숫자의 합에 컷백 k를 뺀 값만큼 지폐를 받는다고 할 때, 받을 수 있는 지폐 수의 기댓값

 

이때, k 이하의 수가 나온다면 최소 1장은 받는다

 

예를 들어 6면체 주사위 2개를 굴리면? 가능한 숫자의 합은 1부터 12까지인데 모든 경우의 수는 36가지이고

 

숫자의 합이 2인 경우의 수는 (1,1)로 1가지

 

3인 경우의 수는 (1,2), (2,1)로 2가지

 

4인 경우의 수는 (1,3), (2,2), (3,1)로 3가지

 

k = 3이면 지폐를 1가지 받는 경우의 수는 숫자의 합이 2, 3, 4 3가지 경우에 가능하다.

 

따라서 지폐 1가지 받는 경우의 수는 1+2+3 = 6가지

 

 

그러면 먼저 m면체 주사위 n개를 굴려서 나올 수 있는 숫자의 합의 모든 경우의 수를 구해야한다

 

n개의 자리에 1부터 m까지 아무 숫자나 하나씩 써 넣으면 된다

 

dp[i][j] = i번째 자리까지 봤을때, 숫자의 합이 j인 경우의 수

 

i = 0,1,2,3,..,n-1까지 가능하고, n개의 자리 각각에 1부터 m까지 들어갈 수 있으므로 총 합은 mn이다.

 

 

0번째 자리에는 1부터 m까지 나올 수 있으므로 i = 1,2,..,m에 대하여 dp[0][i] = 1

 

 

i = 1번부터 n번자리까지는 각 자리에 j = 1,2,3,..,m중 하나를 쓸 수 있고, 현재 숫자의 합이 k이면...

 

dp[i][k] += dp[i-1][k-j]

 

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

for j in range(1,m+1):

    dp[0][j] = 1

for i in range(1,n):

    for j in range(1,m+1):

        for k in range(m*n,-1,-1):

            if k >= j:

                dp[i][k] += dp[i-1][k-j]

 

 

이렇게 하면 dp[n-1]에는 m면체 주사위 n개를 굴려서 나올 수 있는 숫자의 합의 경우의 수가 계산되어 있다

 

따라서 컷백 k이하의 수의 경우에는 지폐 1장을 받을 수 있고, k보다 큰 수에 대해서는 p - k개만큼 지폐를 받으므로

 

일단 가능한 모든 경우의 수를 전부 더해놓은 다음, 마지막에 모든 가능한 경우의 수 m**n으로 나눠야 float error가 최소화된다

 

c = 0

for p in range(n,m*n+1):

    if p <= x:

        c += (dp[n-1][p])

    else:

        c += (dp[n-1][p]*(p-x))

print(c/(m**n))