2133번 타일 채우기

문제

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

입력

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

출력

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

코드

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

int N;
map<int, long long> mp;

void solve()
{
	cin >> N;
	mp[0] = 1;
	mp[1] = 0;
	mp[2] = 3;
	mp[3] = 0;
	long long temp = 0;
	for (int i = 4; i <= N; i++)
	{
		temp += mp[i - 4] * 2;
		if (i % 2 != 0)
			mp[i] = 0;
		else
			mp[i] = mp[i - 2] * 3 + temp;
	}
	cout << mp[N];
}

int main(void)
{
	solve();
	return 0;
}

풀이

N이 홀 수 일때는 칸을 채울 수 없다.

N-2 에서 새로운 형태가 3개 등장하고
N-4 부터는 저렇게 생겼지만 길이가 다르게 2개씩 나온다

연관 : DP