Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

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


크기가 n x 3인 그리드가 있고 그리드의 모든 셀을 세 가지 색상 중 정확히 하나로 칠하려고 한다고 가정합니다. 여기서 사용할 색상은 빨강, 노랑, 녹색입니다.

이제 두 개의 인접한 셀이 동일한 색상을 갖지 않는다는 제약이 있습니다. n개의 그리드 행이 있습니다. 마지막으로 이 격자를 칠할 수 있는 방법의 수를 찾아야 합니다. 답은 매우 클 수 있으므로 모듈로 10^9 + 7을 반환합니다.

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

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

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

  • m =10^9 + 7

  • add() 함수를 정의하면, b,

  • return ((a mod m) + (b mod m)) mod m

  • 주요 방법에서 다음을 수행하십시오 -

  • a123 :=6, a121 =6

  • initialize 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));
}

입력

3

출력

246