leetcode medium : Number of Dice Rolls With Target Sum

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/

Number of Dice Rolls With Target Sum - LeetCode

 

주사위가 n개 있을 때 다 합쳐서 target이 되는 경우의 수를 구하라는 거다.

경우의수... brute force시 exponential한 time complexity.. 이건 분명히 Dynamic Programming의 냄새다. 킁

 

이 문제는 Top-Down DP를 하면 쉽게 풀 수 있다. 즉 재귀적으로 생각해보고 memoization을 적용하는 것이다.

자 예를 들어 주사위가 3개 있다고 가정해보자. 우리에게 익숙하게 각 주사위는 1~6까지 숫자가 있다고 치자. target은 10이다.

3개 주사위 중 한 주사위를 기준으로 생각해보자.

이 주사위가

1이 나오면 -> 나머지 주사위로 9를 만들어야 한다.

2가 나오면 -> 나머지 주사위로 8을 만들어야 한다.

3이 나오면 -> 나머지 주사위로 7을 만들어야 한다.

4가 나오면 -> 나머지 주사위로 6을 만들어야 한다.

5가 나오면 -> 나머지 주사위로 5를 만들어야 한다.

6이 나오면 -> 나머지 주사위로 4를 만들어야 한다.

 

즉 numOfDiceRolls(n=3, f=6, target=10)

=

numOfDiceRolls(n=2, f=6, target=9) +

numOfDiceRolls(n=2, f=6, target=8) +

numOfDiceRolls(n=2, f=6, target=7) +

numOfDiceRolls(n=2, f=6, target=6) +

numOfDiceRolls(n=2, f=6, target=5) +

numOfDiceRolls(n=2, f=6, target=4)

 

일반화 하면

numOfDiceRolls(n, f, target) = numOfDiceRolls(n-1, f, target-1) + numOfDiceRolls(n-1, f, target-2) ... + numOfDiceRolls(n-1, f, target-f)

 

잘보면 f는 고정되어있어서 dp 함수엔 f를 파라미터로 넘길 필요가 없다.

이걸 brute force로 먼저 만들고

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        def dp(n, target):
            if target < 0:
                return 0
            
            if n == 0:
                return 1 if target == 0 else 0
            
            s = 0
            for i in range(1, k + 1):
                s += dp(n - 1, target - i)
            return s
        
        return dp(n, target) % (10**9 + 7)

base케이스만 살짝 잘 봐주면 되는데 target이 음수로 들어오면 무조건 0을 리턴한다. 주사위를 아무리 합쳐도 음수는 만들수가 없으니 그런 경우는 0.

n == 0일때 즉 주사위가 없을때 target=0인 경우는 1이다. 주사위가 없으면 합이 0이니까. target!=0인 경우는 모두 0이다. 그런 경우는 없으니까.

 

memo만 살짝 얹어주면 완성

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        memo = {}
        
        def dp(n, target):
            
            if (n,target) in memo:
                return memo[(n,target)]
            
            if target < 0:
                return 0
            
            if n == 0:
                return 1 if target == 0 else 0
            
            s = 0
            for i in range(1, k + 1):
                s += dp(n - 1, target - i) 
            memo[(n,target)] = s 
            return s
        
        return dp(n, target) % (10**9 + 7)

 

역시 dp는 쉽지 않다.