[C++] 백준 11727번 2xn 타일링2

 

다이나믹 프로그래밍 문제입니다.

 

2xn 직사각형을 2x1과 2x2타일로 채우는 방법의 수를 구하는 문제입니다.

1. i-1칸 까지 채운 상태에서 2x1 세로타일을 채우는 경우

2. i-2칸 까지 채운 상태에서 2x1 가로타일을 위아래로 채우는 경우

3. i-2칸 까지 채운 상태에서 2x2 정사각형타일을 채우는 경우

를 식으로 변경하면

 

memo[i] = memo[i-1] + (memo[i-2] * 2) 가 됩니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int main(int argc, char *argv[])
{
   int n;
   int memo[1000];
   cin >> n;

   memo[0] = 0;
   memo[1] = 1;
   memo[2] = 3;

   for (int i = 3; i <= n; ++i) {
      memo[i] = (memo[i - 1] + memo[i - 2] * 2) % 10007;
   }
   
   cout << memo[n];

   return 0;
}