주사위 시뮬레이터가 각 롤에 대해 1에서 6까지의 난수를 생성한다고 가정합니다. 우리는 생성기가 rollMax[i](1-인덱싱된) 연속 시간보다 더 많은 숫자 i를 굴릴 수 없도록 제너레이터에 제약 조건을 도입하고자 합니다. 정수 rollMax와 정수 n의 배열이 있다고 가정하면 정확한 n개의 롤로 얻을 수 있는 고유한 시퀀스의 수를 반환해야 합니다. 적어도 하나의 요소가 서로 다른 경우 두 시퀀스는 다른 것으로 간주됩니다. 따라서 n이 2이면 rollMax =[1,1,2,2,2,3]이면 출력은 34가 됩니다. 따라서 주사위에는 2개의 주사위가 있고, 제약 조건이 없으면 주사위에는 다음이 있습니다. 6*6 =36개의 가능한 조합, 이 경우 숫자 1과 2는 최대 한 번 연속해서 나타나므로 시퀀스 (1,1) 및 (2,2)가 발생할 수 없습니다. 따라서 최종 답은 36 – 2 =34가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- dfs()라는 메서드를 하나 생성합니다. 이것은 dieLeft, last, currLen, 배열 r 및 행렬 dp를 사용합니다.
- dieLeft =0이면 1을 반환
- dp[dieLeft][last][currLen]이 -1이 아니면 dp[dieLeft, last, currLen]을 반환합니다.
- 카운터:=0
- 0에서 6 사이의 i에 대해
- i =last 및 r[i] =currLen이면 다음 부분을 건너뛰고 다음 반복으로 이동합니다.
- counter :=dfs(dieLeft – 1, i, currLen + i =last일 때 1, 그렇지 않으면 1, r, dp)
- dp[dieLeft, last, currLen] :=카운터
- dp[dieLeft, last, currLeft]를 반환
- 주요 방법은 다음과 같습니다 -
- dp of order (n + 1) x 6 x 16이라는 하나의 3D 배열을 만들고 -1로 채웁니다.
- dfs(n, 0, 0, rollMax, dp)를 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
class Solution {
public:
int dfs(int dieLeft, int last, int currLen, vector <int> &r,vector < vector < vector <int> > > &dp){
if(dieLeft == 0){
return 1;
}
if(dp[dieLeft][last][currLen]!=-1)return dp[dieLeft][last][currLen];
int counter = 0;
for(int i =0;i<6;i++){
if(i==last && r[i] == currLen)continue;
counter = (counter%mod + (dfs(dieLeft-1,i,i==last?currLen+1:1,r,dp))%mod)%mod;
}
dp[dieLeft][last][currLen] = counter%mod;
return dp[dieLeft][last][currLen]%mod;
}
int dieSimulator(int n, vector<int>& rollMax) {
vector < vector < vector <int> > > dp(n+1, vector < vector <int> > (6, vector <int>(16, -1)));
return dfs(n,0,0,rollMax, dp)%mod;
}
};
main(){
vector<int> v = {1,1,2,2,2,3};
Solution ob;
cout << (ob.dieSimulator(2,v));
} 입력
2 [1,1,2,2,2,3]
출력
34