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

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

---

DP 문제.

int dp[d+1][target+1]; // dp[d][sum] = d개의 dice로 sum을 만들 수 있는 경우의 수

점화식은 위와 같다.

먼저 dp[1][1~target]을 1로 초기화 시킨다. (다이스 1개로 만들 수 있는 경우의 수 세팅)

dp 배열을 행우선탐색으로 탐색하면서 배열을 채운다.

 

(dice, sum) dp 요소를 채운다고 할 때,

for(int face=1; face<=f; face++){
    if(sum-face < 0) break; // 배열 벗어나는 거 방지
    dp[dice][sum] = (dp[dice][sum] + dp[dice-1][sum-face]) % MOD;                
}

dice의 숫자를 모두 탐색하면서 sum을 만들 수 있는 경우의 수를 모두 더하면 된다.

예를 들어, d=2, f=6, target=7일 때,

dice[2][4]를 채울 수 있는 경우는 1+3, 2+2, 3+1 이다. 

즉, face가 1,2,3일 때 dp[1][3], dp[1][2], dp[1][1]을 더해서 구한다.

 

시간복잡도는 배열을 모두 채우는데 드는 시간인 O(d * f * target)이다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1155.%20Number%20of%20Dice%20Rolls%20With%20Target%20Sum.cpp