LeetCode 솔루션 분류
1155. Number of Dice Rolls With Target Sum
본문
[Medium]
You have n dice and each die has k faces numbered from 1 to k.
Given three integers n, k, and target, return the number of possible ways (out of the kn total ways) to roll the dice so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 109 + 7.
You have n dice and each die has k faces numbered from 1 to k.
Given three integers n, k, and target, return the number of possible ways (out of the kn total ways) to roll the dice so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: n = 1, k = 6, target = 3 Output: 1 Explanation: You throw one die with 6 faces. There is only one way to get a sum of 3.
Example 2:
Input: n = 2, k = 6, target = 7 Output: 6 Explanation: You throw two dice, each with 6 faces. There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.
Example 3:
Input: n = 30, k = 30, target = 500 Output: 222616187 Explanation: The answer must be returned modulo 109 + 7.
Constraints:
1 <= n, k <= 301 <= target <= 1000
관련자료
-
링크
댓글 1
Coffee님의 댓글
- 익명
- 작성일
Runtime: 17 ms, faster than 82.26% of Java online submissions for Number of Dice Rolls With Target Sum.
Memory Usage: 41.6 MB, less than 78.98% of Java online submissions for Number of Dice Rolls With Target Sum.
Memory Usage: 41.6 MB, less than 78.98% of Java online submissions for Number of Dice Rolls With Target Sum.
class Solution {
private final int MODULO = 1000000007;
private Integer[][] cache;
private int n = 0;
private int k = 0;
public int numRollsToTarget(int n, int k, int target) {
this.n = n;
this.k = k;
this.cache = new Integer[n+1][target+1];
return dp(0, target);
}
public int dp(int i, int remain){
// escape condition
if(i == n && remain == 0){
return 1;
}
if(i > n || remain < 0){
return 0;
}
if(cache[i][remain] != null){
return cache[i][remain];
}
int ans = 0;
for(int num = 1; num <= k; num++) {
ans += dp(i + 1, remain - num);
ans %= MODULO;
}
return cache[i][remain] = ans;
}
}
