[C++] 백준 2133번 타일 채우기

 

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

 

3*n의 사각형에 타일을 채울 때 경우의 수를 구하는 문제입니다.

 

1) n이 홀수이면 경우의수는 0입니다.

2) n이 2일때 3가지 경우의 수가 있습니다.

3) 그리고 n이 4일때는 2가지 경우의 수가 늘어나게 됩니다.

 

1~3의 코드는 다음과 같습니다.

 

1)

if (n % 2 == 1) {
 	cout << "0" << endl;
 	return 0;
}

 

2), 3)

for (int i = 4; i <= n; i += 2) {
 	memo[i] = memo[i - 2] * 3;            // 2)

 	for (int j = 4; i - j >= 0; j += 2) {
 		memo[i] += memo[i - j] * 2;   // 3)
 	}
}

 

#include <iostream>
using namespace std;

int memo[40] = {0, };

int main(int argc, char *argv[])
{
   int n;
   int result = 0;

   cin >> n;
   
   memo[0] = 1;
   memo[2] = 3;

   if (n % 2 == 1) {
      cout << "0" << endl;
      return 0;
   }

   for (int i = 4; i <= n; i += 2) {
      memo[i] = memo[i - 2] * 3;

      for (int j = 4; i - j >= 0; j += 2) {
         memo[i] += memo[i - j] * 2;
      }
   }

   cout << memo[n] << endl;
   return 0;
}