DP 문제 Number of dice rolls with target

주사위 면의 수 f인 (1...f) d 개의 주사위를 굴려 target을 만드는 경우의 수를 구하시오.

 

문제 및 예제의 원본이다.

 

문제를 딱 보고 든 풀 수 있는 방법 중 하나는 DFS, BFS 였다. 하지만 DFS, BFS로 하면 30면 짜리 주사위의 30개를 굴려서 특정 target이 될 수 있는 경우의 수를 구할 때 시간초과(TLE)가 날 수 있다.

 

그렇다면 다른 방법으로 풀 수 있는 게 무엇일까 생각해봤다.

DP 방법의 풀이가 가능한 지 알아보자. 일단 2차식 형태의 점화식을 세워보자. (여기서 2차식이라 함은 이차원 배열을 사용한다고 생각하면 된다.)

dp[d][k]를 주사위 d개로 t를 만들 수 있는 경우의 수라고 하자. (항상 dp에서는 점화식을 어떻게 정의하느냐가 중요하다.)

 

dp[d][t] = dp[d-1][1] + dp[d-1][2] + ... + dp[d-1][t-1]로 표현할 수 있고, 자세히 설명하자면 d-1 개의 주사위를 활용해서 1을 만드는 경우의 수에 나머지 한 개의 주사위에서 t-1이 되는 경우의 수.

따라서 dp[d-1][1]은 실질적으로 dp[d-1][1] * 1(1은 주사위에서 t-1이 나오는 경우의 수) 이다.

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        # optimized solution
        # Using DP Knapsack
        dp = [[0 for _ in range(dd * f + 1)] for dd in range(d + 1)]

        if target == 0 or target > d * f:
            return 0

        for i in range(1, f + 1):
            dp[1][i] = 1

        MOD = 10 ** 9 + 7
        for i in range(2, d + 1):
            for j in range(1, target + 1):
                for k in range(1, f + 1):
                    if 0 <= j - k < len(dp[i - 1]):
                        dp[i][j] += dp[i - 1][j - k]

        return dp[d][target] % MOD

    def numRollsToTarget2(self, d:int, f:int, target: int) ->int:

        dp = [[0 for _ in range(dd * f + 1)] for dd in range(d + 1)]

        if target == 0 or target > d * f:
            return 0

        for i in range(1, f + 1):
            dp[1][i] = 1

        MOD = 10 ** 9 + 7
        for i in range(2, d + 1):
            for j in range(i, d * f + 1):
                for k in range(1, f + 1):
                    if 0 <= j - k < len(dp[i - 1]):
                        dp[i][j] += dp[i - 1][j - k]

        return dp[d][target] % MOD

두 번째 풀이가 내가 푼 방법인데, 시간이 오래 걸린다. 왜냐면 j 의 범위를 i 부터 d * f +1 까지로 했기 때문에 target 보다 큰 부분도 살피기 때문에 연산시간이 오래 걸린다. 이를 줄이려면 첫 번째 풀이처럼 하는 것을 추천한다.