1155. Number of Dice Rolls With Target Sum

• k개의 면을 가진 n개의 주사위를 굴려서 나온 눈의 합으로 주어진 숫자 target을 만들 수 있는 경우의 수를 구한다.

• 주사위를 하나씩 던지면서 나온 숫자에 따라 target을 감소 시키면서 결과적으로 0이 될 때까지 탐색을 진행한다.
• n개의 주사위 중 첫번째 주사위를 던졌을 때 1 ~ k까지의 숫자가 등장하는 경우의 수가 존재하며 각각에 대해서 나머지 n - 1개의 주사위를 던져서 눈의 합이 target - 나온 숫자 가 되도록 하면 된다.
• 만일 target이 0보다 작은 경우 잘못된 조합에 해당되므로 경우의 수는 0이다.
• 마찬가지로 남아있는 주사위의 수가 없는데 target이 0이 아닌 경우에도 잘못된 조합에 해당되므로 경우의 수는 0이다.
• 남아있는 주사위의 수도 없고 target도 0이라면 다른 경우의 수가 없으므로 결과는 1이 된다.

• 특정 개수의 주사위로 특정 target 숫자를 만드는 경우의 수는 항상 동일하므로 memoization을 통해서 계산 속도를 높인다.
• 이 때 로직을 단순화하기 위해서 주사위의 수가 0이면서 target 값이 0이 아닌 경우는 미리 값을 0으로 초기화 해둔다.
• 주사위의 수가 0이면서 target 값이 0이 아닌 경우는 미리 값을 1로 초기화 해둔다.

class Solution {
    final int MOD = 1_000_000_000 + 7;
    
    int traverse(int n, int k, int target, int[][] dp) {
        if (target < 0) return 0;
        if (dp[n][target] != -1)
            return dp[n][target];
        int result = 0;
        for (int i = 1; i <= k; ++i) {
            result = (result + traverse(n - 1, k, target - i, dp)) % MOD;
        }
        return dp[n][target] = result;
    }
    
    public int numRollsToTarget(int n, int k, int target) {
        int[][] dp = new int[n + 1][target + 1];
        for (int[] sub : dp) {
            Arrays.fill(sub, -1);
        }
        Arrays.fill(dp[0], 0);
        dp[0][0] = 1;
        return traverse(n, k, target, dp);
    }
}