Leetcode - 1155. Number of Dice Rolls With Target Sum

문제

k개의 면을 가진 주사위 n개가 존재한다. 이 주사위 n개를 던졌을때, 그 합이 target값이 나오는 경우의 수를 구하라. 결과 값은 % 1000000007 으로 모듈러 연산해서 리턴하라(오버플로우 발생예방)

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.

각각의 주사위 값은 유니크하다. (1,6) (6,1)은 독립적인 경우의 수다.

Back Tracking (Brute-force 방법)

먼저 생각해 볼 수 있는 방법은, Back Tracking으로 완전탐색 하는것이다. n을 하나씩 줄이면서 다음 재귀함수를 호추하고 인자로 현재 sum을 넘긴다. 그리고 sum==target일때, 1을 리턴한다. 결과는 TLE가 발생한다.

// n: number of k-faces dice
class Solution {
    vector<vector<int>> memo;
    int total;
    int bt(int n, int face, int sum, int tgt) { 
        /* base case */
        if (n == 0) {
            if (sum == tgt) //found
                return 1;
            return 0;
        }

        int way = 0;
        for (int i = 1; i <= face; i++) {
            way = (way + bt(n - 1, face, sum + i, tgt)) % 1000000007;
        }
        return way;
    }
public:
    int numRollsToTarget(int n, int k, int target) {
        memo = vector<vector<int>>(n + 1, vector<int>(target + 1, -1));
        return bt(n, k, 0, target);
    }
};

해결 DP (top-down with memoization)

[주사위 번호] 현재까지 합 이라고 해보자. 예시로 n:3 k:3 target:7이 주어진다. 이를 그림으로 풀어가보면 아래와 같이 (주사위번호, 현재까지 합) 에 따른 중복된 재귀호출을 발견할 수 있다. 따라서 이부분은 memoization을 한다.

                       [0]1   ...
             +1          +2         +3
        [1]2           [1]3          [1]4
   +1   +2  +3
[2]3 [2]4 [2]5    [2]4 [2]5 [2]6     ...
      ^^^  ^^^     ^^^  ^^^ 중복된 호출들

위의 Back Tracking 구조에서 memo[] 처리 부분만 추가한다.

// n: number of k-faces dice
class Solution {
    vector<vector<int>> memo;
    int total;
    int bt(int n, int face, int sum, int tgt) {
        /* base case */
        if (sum > tgt) // sum이 memo[]배열을 초과할경우 에러 예방
            return 0;
        if (n == 0) {
            if (sum == tgt) //found
                return 1;
            return 0;
        }
        if (memo[n][sum] != -1)
            return memo[n][sum];
            
        int way = 0;
        for (int i = 1; i <= face; i++) {
            // bt() with unique (n, sum) is calculated repeatedly. and it return the same result, so memoize it.
            way = (way + bt(n - 1, face, sum + i, tgt)) % 1000000007;
        }
        memo[n][sum] = way;
        return memo[n][sum];
    }
public:
    int numRollsToTarget(int n, int k, int target) {
        memo = vector<vector<int>>(n + 1, vector<int>(target + 1, -1));
        return bt(n, k, 0, target);
    }
};