파이썬에서 n개의 주사위를 던질 수 있는 방법의 수를 세는 프로그램

<시간/>

숫자 n, 면의 수, 합계 값이 있다고 가정하고 면이 있는 n개의 주사위를 던지면 합계를 얻을 수 있는 방법의 수를 찾아야 합니다. 답변이 매우 큰 경우 결과는 10**9 + 7입니다.

따라서 입력이 n =2개의 면 =6 총 =8과 같으면 2개의 6면 주사위로 8을 만드는 5가지 방법이 있으므로 출력은 5가 됩니다. (2 및 6), (6 및 2) , (3 및 5), (5 및 3), (4 및 4).

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m :=10^9 + 7
dp :=크기 목록(총 + 1) 다음 0으로 채우기
범위 1에서 최소 얼굴까지의 얼굴에 대해 각 단계에서 총 + 1씩 업데이트합니다.
- dp[얼굴] :=1
범위 0에서 n - 2에 있는 i에 대해 수행
- 총 범위가 0인 j에 대해 1 감소, 수행
- dp[j] :=j - f>=1
  일 때 범위 1에서 면 + 1까지 f에 대한 모든 dp[j - f]의 합
dp mod m
의 마지막 요소를 반환합니다.

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

class Solution:
   def solve(self, n, faces, total):
      m = 10 ** 9 + 7
      dp = [0] * (total + 1)

      for face in range(1, min(faces, total) + 1):
         dp[face] = 1
      for i in range(n - 1):
         for j in range(total, 0, -1):
            dp[j] = sum(dp[j - f] for f in range(1, faces + 1) if j - f >= 1)
      return dp[-1] % m
ob = Solution()
n = 2
faces = 6
total = 8
print(ob.solve(n, faces, total))

입력

2,6,8