- toc {:toc}
풀이
손으로 경우의 수를 구해보고 규칙성을 생각해본다.
- 3x2의 경우
다음의 3가지 경우가 존재한다.
- 3x4의 경우
d의 왼쪽 큰 직사각형에서 3가지 경우, 오른쪽에서 3가지 경우가 있으므로 3x3 = 9
e와 같이 새로운 경우 2가지 존재하므로 9+2 = 11
- 3x6의 경우
f에서 왼쪽 큰 직사각형은 11가지의 경우를 넣을 수 있고, f 오른쪽 부분은 3가지 경우의 수가 있기 때문에 11x3 = 33
f의 경우를 셀 때 a, b, c 의 구조로 이루어진 경우의 수를 확인했으나, e의 경우의 수는 절반만 확인한 셈이기 때문에 e의 경우가 오른쪽에 위치한 경우도 확인해줘야 한다.
차근차근 생각해보자. f의 경우에서 e의 경우를 빼고 생각해보자.
먼저, e의 경우를 제외하고 a, b, c의 경우만 생각해보면 d의 경우의 수(3x3)에 f의 오른쪽 6개의 정사각형에서 만들 수 있는 경우의 수 3개를 곱해 a, b, c 의 모양만 생각하면 3x3x3 = 27 개의 경우의 수를 확인했다.
다음, e의 경우의 수를 생각해보자. e의 모양이 나올 수 있는 경우의 수는 ㅡ모양이 위에 위치한 경우, 아래에 위치한 경우 2가지이고, g의 경우에서 왼쪽에는 a, b, c 3가지 경우가 나올 수 있기 때문에 3x2 로 셀 수 있다. 추가로, e의 모양이 g의 오른쪽 끝에 위치할 수도 있고, 왼쪽 끝에 위치할 수도 있기 때문에 3x2x2 = 12 가 된다. 때문에 f에서 11x3의 의미는 (a, b, c의 모양을 사용한 경우의 수) + (g의 경우의 수 / 2) 인 셈이다.
추가로 h의 새로운 경우 2가지가 존재한다.
때문에 최종적으로 11x3 + 3x2 + 2 = 41이다.
이제 3x2, 3x4, 3x6의 규칙성을 생각해보면 아래처럼 표현할 수 있다.
dp[0] = 1;
dp[2] = dp[2-2] * 3;
dp[4] = dp[4-2] * 3 + dp[4-4] * 2;
dp[6] = dp[6-2] * 3 + dp[6-4] * 2 + dp[6-6] * 2;#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int dp[33];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
if(n % 2 == 1){
cout << 0 << endl;
exit(0);
}
dp[0] = 1;
for(int i=2; i<=n; i+=2){
for(int j=2; j<=i; j+=2){
int first = i-(i-j), factor;
if(first == 2) factor = 3;
else factor = 2;
dp[i] += dp[i-j] * factor;
}
}
cout << dp[n] << endl;
return 0;
}