[LeetCode] 1155. Number of Dice Rolls With Target Sum - 동적계획법(Dynamic Programming) JAVA

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/description/?envType=problem-list-v2&envId=dynamic-programming

코드설명

동적계획법(Dynamic Programming) 을 활용합니다.

 

처음에 놓쳣었던 부분은, MOD = 10^9 + 7 을 그대로 사용한 점입니다. 자바에서는 10^9가 거듭 제곱이 아닌 XOR 연산으로 해석됩니다. 따라서 MOD 값을 1000000007로 명시적으로 작성해야 합니다.

int MOD = 1000000007;

해당 구조에서 cache[level][sum]으로 level, 즉 주사위를 level개 사용하여, sum의 합만큼 나타내었을때의 가능한 주사위 개수를 반환해가면서 처리하면 중복계산값을 제거하여 계산할 수 있습니다.

 

 

코드

class Solution {
    int[][] cache;
    int MOD = 1000000007;
    public int numRollsToTarget(int n, int k, int target) {
        cache = new int[31][1001];
        for(int i=0; i<31; i++){
            Arrays.fill(cache[i], -1);
        }
        DFS(n, target, k);
        return cache[n][target];
    }

    int DFS(int level, int sum, int k){
        if(level == 0 && sum == 0){
            return 1;
        }
        if(cache[level][sum] != -1) return cache[level][sum] % MOD;
        int ret = 0;
        for(int i=1; i<=k; i++){
            if(sum -i >=0 && level -1 >= 0){
                ret = (ret + DFS(level - 1, sum - i, k) % MOD) % MOD;
            }
        }
        return cache[level][sum] = ret % MOD;
    }
}