[LeetCode] 1155. Number of Dice Rolls With Target Sum

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.

 

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 <= 30
• 1 <= target <= 1000

---

문제 풀이

• 주사위를 던질 수 있는 개수는 n, 주사위의 눈금은 k, 모든 주사위를 던저 합한 값이 target 일 조건의 갯수를 구해야한다.
• Backtracking 으로 완전탐색을 시도하여 문제를 풀 수 있다. 
• 하지만 n 의 갯수가 최대 30 이기 때문에, 그리고 k 값도 30 일 수 있어서 시간 초과가 날 수 있다. 
• 재귀함수 호출시 브랜치가 30 이면 각 노드 레벨에서 30 개의 브랜치를 타고 들어가기 때문에, 30^30 까지 진행될 수 있다. 
• 그래서 각 n 개의 주사위를 던졌을때 계산된 갯수를 메모이제이션을 활용하여 리턴해야한다. 
• Bottom-up 으로 풀때, 종료 조건은 우선 n 개를 모두 던졌지만 target 에 도달했을때랑 도달하지 못했을때 리턴을 해준다. 
• 그리고 가지치기로 해쉬 테이블에 n 번 던졌을때 합이 있다면 더 이상 재귀호출을 하지않고 이미 구해서 저장된 값을 리턴한다.
• 해쉬 테이블을 사용하지 않고 @lru_cache 를 사용해도 무방하다.

소스코드

해쉬 테이블 사용

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        hash_table = defaultdict()
        mod = 10**9 + 7
        def rec(n, t):
            if (n, t) in hash_table:
                return hash_table[(n, t)]
            
            if n == 0 and t != 0:
                return 0
            if n == 0 and t == 0:
                return 1
            
            total = 0
            for i in range(1, k + 1):
                total += rec(n - 1, t - i)
            hash_table[(n, t)] = total
            return total % mod
        return rec(n, target)

@lru_cache 사용

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        mod = 10**9 + 7
        @lru_cache(maxsize=None)
        def rec(n, t):
            if n == 0 and t != 0:
                return 0
            if n == 0 and t == 0:
                return 1
            
            total = 0
            for i in range(1, k + 1):
                total += rec(n - 1, t - i)
            return total % mod
        return rec(n, target)