[백준/BOJ] 백준 11727번 : 2×n 타일링 2

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

11727번: 2×n 타일링 2

왼쪽부터 2*1 타일로 채우는 경우, 1*2 타일(2개)로 채우는 경우, 2*2 타일로 채우는 경우를 고려해서 방법의 수를 구한다

 

코드

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

int cache[1001];

int Solve(int n)
{
	//기저사례
	if (n == 2)
		return 3;
	else if (n == 1)
		return 1;

	int& ret = cache[n];

	//계산한적이 있을때
	if (ret != -1)
		return ret;

	//왼쪽부터 2*1타일로 채우는 경우, 1*2 타일(2개)로 채우는 경우, 2*2타일로 채우는 경우를 고려한다
	ret = Solve(n - 1) + Solve(n - 2) + Solve(n - 2);
	ret %= 10007;

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	memset(cache, -1, sizeof(cache));

	int n;
	cin >> n;

	cout << Solve(n);

	return 0;
}