Domino와 Tromino의 두 가지 유형의 모양이 있다고 가정합니다. 아래와 같이 회전할 수 있습니다 -
타일링에서 모든 사각형은 타일로 덮여 있어야 합니다. 여기서 두 타일은 보드에 4방향으로 인접한 두 개의 셀이 있고 타일 중 정확히 하나가 타일이 차지하는 두 사각형이 모두 있는 경우에만 다릅니다.
N이 주어지면 2xN 보드를 타일링할 수 있는 방법의 수를 찾아야 합니다. 따라서 입력이 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]
예시(C++)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#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 numTilings(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.numTilings(3)); }
입력
3
출력
5