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

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

Number of Dice Rolls With Target Sum - LeetCode

leetcode - 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 10^9 + 7.

 

당신은 n개의 주사위가 있고, k개의 면이 주어진다. (1부터 k까지의 수)

정수 n, k, target이 주어진다. n개의 주사위를 굴려서 나온 수의 합이 target이 되는 경우의 수를 모두 구하시오. 값이 커질 수 있기 때문에, 1e9+7로 나누세요.

 

 

풀이

탑다운 또는 바텀업 방식으로 풀 수 있다.

dp테이블을 dp[n][target] = n개의 주사위로 target을 만드는 경우의 수로 한다.

 

탑다운 방식의 풀이)

재귀적으로 dp 를 풀면서, 1부터 k까지의 주사위를 굴리는 모든 경우를 전개시킨다.

남은 주사위 수와 남은 target을 넣어 재귀적으로 구한다.

 

바텀업 방식의 풀이)

2차원배열을 돌리면서 dp[i][j]에 dp[i-1][j-k] ~ dp[i-1][j-1]의 값들을 누적시킨다.

 

코드

C++

 

탑다운 코드

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
private:
    const int MOD = 1e9+7;  
    vector<vector<int>> dp;  

public:
    int solve(int left, int k, int target) {
        if(left == 0) {
            if(target == 0) return 1;
            return 0;
        }
        
        if(dp[left][target] != -1) return dp[left][target];
        
        int answer = 0;
        for(int i = 1; i <= k; i++) {
            if(target-i < 0) continue;
            answer = (answer + solve(left-1, k, target-i))%MOD;
        }
        return dp[left][target] = answer;
        
    }

    int numRollsToTarget(int n, int k, int target) {
        dp.resize(n+1, vector<int>(target+1, -1));

        return solve(n, k, target);
    }
};

 

 

바텀업 코드

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        const int MOD = 1e9+7;
        vector<vector<int>> dp(n+1, vector<int>(target+1, 0));
        dp[0][0] = 1;

        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= target; j++) {
                for(int face = 1; face <= k; face++) {
                    if(j-face < 0) continue;
                    dp[i][j] = (dp[i][j] + dp[i-1][j-face]) % MOD;
                }
            }
        }

        return dp[n][target];
    }
};