C++에서 N × 3 그리드를 그리는 방법의 수

크기가 n x 3인 격자가 있고 격자의 각 셀을 세 가지 색상 중 정확히 하나로 칠하려고 한다고 가정합니다. 색상은 빨간색, 노란색 또는 녹색입니다. 이제 두 개의 인접한 셀이 동일한 색상을 갖지 않는다는 제약 조건이 있습니다. 그리드의 행 수는 n입니다. 우리는 이 격자를 칠할 수 있는 방법의 수를 찾아야 합니다. 답은 매우 클 수 있으므로 모듈로 10^9 + 7을 반환합니다.

따라서 입력이 1과 같으면 출력은 12가 됩니다.

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

m =1^9 + 7
add() 함수를 정의하면, b,
return ((a mod m) + (b mod m)) mod m
주요 방법에서 다음을 수행하십시오 -
a123 :=6, a121 =6
i:=2 초기화의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
- b121 :=add(3 * a121, 2 * a123)
- b123 :=add(2 * a121, 2 * a123)
- a121 :=b121
- a123 :=b123
return add(a123, a121)

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

예

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli mod = 1e9 + 7;
class Solution {
   public:
   lli add(lli a, lli b){
      return ((a % mod) + (b % mod)) % mod;
   }
   int numOfWays(int n){
      lli a123 = 6, a121 = 6;
      lli b123, b121;
      for (int i = 2; i <= n; i++) {
         b121 = add(3 * a121, 2 * a123);
         b123 = add(2 * a121, 2 * a123);
         a121 = b121;
         a123 = b123;
      }
      return add(a123, a121);
   }
};
main(){
   Solution ob;
   cout << (ob.numOfWays(3));
}