d개의 주사위가 있고 각 주사위에는 1, 2, ..., f로 번호가 매겨진 f개의 면이 있다고 가정합니다. 우리는 주사위를 굴리기 위해 가능한 방법의 수(총 fd 중에서)를 모듈로 10^9 + 7로 찾아야 앞면이 보이는 숫자의 합이 목표와 같도록 해야 합니다. 따라서 입력이 d =2, f =6, target =7과 같으면 출력은 6이 됩니다. 따라서 각 주사위를 6면으로 던진다면 합 6을 얻는 방법은 1 + 6, 2 + 5, 3 + 3, 4 + 3, 5 + 2, 6 + 1.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- m :=1e9 + 7
- d x (t + 1) 차수의 테이블 dp를 만들고 이것을 0으로 채웁니다.
- 0 ~ d – 1 범위의 i에 대해
- 0 ~ t
- 범위의 j에 대해
- i =0이면 dp[i, j] :=j가 범위 1에서 f일 때 1, 그렇지 않으면 0
- 그렇지 않으면
- 1에서 f
- 범위의 l에 대해
- j – l> 0이면 dp[i, j] :=dp[i, j] + dp[i – 1, j - l] 및 dp[i,j] :=dp[i, j] 모드 m
- 1에서 f
- 0 ~ t
- dp[d – 1, t] mod m을 반환
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class Solution(object): def numRollsToTarget(self, d, f, t): mod = 1000000000+7 dp =[[0 for i in range(t+1)] for j in range(d)] for i in range(d): for j in range(t+1): if i == 0: dp[i][j] = 1 if j>=1 and j<=f else 0 else: for l in range(1,f+1): if j-l>0: dp[i][j]+=dp[i-1][j-l] dp[i][j]%=mod return dp [d-1][t] % mod ob = Solution() print(ob.numRollsToTarget(2,6,7))
입력
2 6 7
출력
6