C++에서 도미노와 트로미노로 영역을 채우기 위해 구성 수를 계산하는 프로그램이 있습니다.

Domino와 Tromino의 두 가지 모양이 있다고 가정합니다. 도미노는 2 x 1 모양이고 트로미노는 'L'자 모양입니다. 아래와 같이 회전할 수 있습니다 -

숫자 n이 있는 경우 이 두 가지 유형의 조각으로 2 x n 보드를 채우는 구성의 수를 찾아야 합니다. 타일링에서 알 수 있듯이 모든 사각형은 타일로 덮여 있어야 합니다.

따라서 입력이 3이면 출력은 5가 됩니다. 따라서 배열은 [XYZ XXZ XYY XXY XYY] 및 [XYZ YYZ XZZ XYY XXY]가 될 수 있습니다. 여기에서 다른 문자는 다른 타일에 사용됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

크기가 N + 5인 dp라는 배열을 만들고 dp[1] :=1, dp[2] :=2 및 dp[3] :=5로 설정
범위 4에서 N까지의 i에 대해
- dp[i] :=2*dp[i − 1] + dp[i − 3]
반환 dp[N]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int add(int a, int b){
   return ((a % MOD) + (b % MOD)) % MOD;
}
class Solution {
   public:
   int solve(int N) {
      vector <int> dp(N + 5);
      dp[1] = 1;
      dp[2] = 2;
      dp[3] = 5;
      for(int i = 4; i <= N; i++){
         dp[i] = add(2 * dp[i − 1], dp[i − 3]);
      }
      return dp[N];
   }
};
main(){
   Solution ob;
   cout << (ob.solve(3));
}