Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 주사위 굴림 시뮬레이션: DFS와 메모이제이션으로 풀기

문제 개요

주사위 시뮬레이터가 매번 굴릴 때마다 1부터 6 사이의 난수를 생성한다고 가정해 봅시다. 여기에 하나의 제약 조건을 추가하려고 합니다. 바로 어떤 숫자 i든 연속해서 rollMax[i]번(1-인덱스 기준)을 초과하여 나올 수 없도록 하는 것입니다. 정수 배열 rollMax와 정수 n이 주어질 때, 정확히 n번 굴려서 얻을 수 있는 서로 다른 수열의 개수를 반환해야 합니다. 두 수열은 적어도 하나의 원소가 서로 다를 때 다른 수열로 간주됩니다.

예를 들어 n = 2이고 rollMax = [1,1,2,2,2,3]이라면 출력은 34입니다. 제약 조건이 없다면 주사위를 두 번 굴릴 때 6 × 6 = 36가지 조합이 존재하지만, 이 설정에서는 숫자 1과 2가 연속으로 최대 한 번만 나올 수 있으므로 수열 (1,1)과 (2,2)는 만들어질 수 없습니다. 따라서 최종 답은 36 − 2 = 34가 됩니다.

풀이 접근 방법

이 문제는 재귀적 DFS(깊이 우선 탐색)에 메모이제이션을 결합한 동적 계획법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 세 가지 상태, 즉 남은 굴림 횟수(dieLeft), 직전에 나온 숫자(last), 그 숫자가 연속으로 나온 횟수(currLen)를 기준으로 중간 결과를 캐싱하는 것입니다.

알고리즘 단계는 다음과 같습니다.

  1. dfs() 메서드 작성: dieLeft(남은 굴림 횟수), last(직전 숫자), currLen(연속 등장 횟수), 배열 r, 3차원 행렬 dp를 인자로 받습니다.
  2. 종료 조건: dieLeft가 0이면 유효한 수열 하나를 완성한 것이므로 1을 반환합니다.
  3. 메모이제이션 확인: dp[dieLeft][last][currLen] 값이 -1이 아니라면 이미 계산된 결과이므로 즉시 반환합니다.
  4. 탐색: counter를 0으로 초기화한 뒤, i를 0부터 5까지 반복합니다.
    • i == last이면서 r[i] == currLen이면 제약 조건을 위반하므로 해당 경우는 건너뜁니다.
    • 그렇지 않으면 counter에 dfs(dieLeft − 1, i, i == last ? currLen + 1 : 1, r, dp)의 반환값을 더합니다. 같은 숫자가 다시 나오면 연속 길이를 1 늘리고, 다른 숫자가 나오면 길이를 1로 초기화하는 논리입니다.
  5. 캐싱 후 반환: 계산된 counter를 dp[dieLeft][last][currLen]에 저장한 뒤 반환합니다.

메인 함수 구성

  • (n + 1) × 6 × 16 크기의 3차원 배열 dp를 생성하고 모든 값을 -1로 초기화합니다. rollMax의 각 원소는 최대 15이므로 연속 길이 차원의 크기를 16으로 잡으면 충분합니다.
  • dfs(n, 0, 0, rollMax, dp)를 호출해 최종 결과를 반환합니다.

결과값이 매우 커질 수 있으므로, 코드에서는 10⁹ + 7로 나눈 나머지를 취해 오버플로를 방지합니다.

C++ 구현 예제

#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;
    }
};
int 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

복잡도 분석

상태 공간의 크기는 n × 6 × 15이며, 각 상태에서 최대 6개의 전이를 고려하므로 시간 복잡도는 O(n × 36), 즉 n에 비례합니다. 공간 복잡도 역시 메모이제이션 테이블 크기에 비례하여 O(n × 6 × 16)입니다. 완전 탐색만으로는 지수적으로 증가하는 경우의 수를 감당할 수 없지만, 메모이제이션을 통해 중복 계산을 제거함으로써 실용적인 시간 안에 정답을 구할 수 있습니다.