백준 2133 c++ 타일 채우기

https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

---

 

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

 

---

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

int main()
{
	int N;
	cin >> N;
	vector<int> dp(N+1, 0);
	dp[0] = 1;//2x0의 공간을 채울 수 있는 경우의 수는 1개
	dp[2] = 3;//2x2의 공간을 채울 수 있는 경우의 수는 2개
	for (int i = 4; i <= N; i = i + 2)
	{
		dp[i] = dp[i - 2] * 3;
		for (int j = 0; j < i-2; j=j+2)
		{
			dp[i] = dp[i] + dp[j]*2;
		}
	}
	cout << dp[N];
}

---

dp[2] 는 다음과 같이 3개이다

dp[4]는 dp[2] 3가지에 더해서 또 위와같이 3가지 경우의 수가 더 올 수 있으므로 3 x 3 이다.

그러나 dp[4]의 경우 그 고유한 배열을 2가지 가지고 있다.

3x4의 고유한 배열

위의 2가지 경우를 더해 dp[4] = 11이 된다.

dp[6]의 경우

3x6 고유배열

dp[4]에 3x2 칸이 올 경우의 수(3)를 곱해준값 + 

dp[2] 에 3x4의 고유한 배열이 올 경우의 수 (2)를 곱해준 값 +

dp[6]의 고유의 값

이 될 것이다.

즉 dp[6] = dp[4] x 3 + dp[2] x 2 + 1 x 2

              = dp[4] x 3 + dp[2] x 2 + dp[0] x 2