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

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

11726번: 2×n 타일링

2Xn 직사각형을 왼쪽부터 2X1타일로 채운 경우와, 1X2타일 2개로 채운 경우를 모두 고려한다.

 

코드

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

int cache[1001];
int MOD = 10007;

int solve(int n)
{

	//기저 사례
	if (n == 2)
		return 2;
	else if (n == 1)
		return 1;

	int& ret = cache[n];

	//ret가 -1이 아니면 이전에 계산했던것이다
	if (ret != -1)
		return ret;

	//왼쪽을 2X1타일로 채운 경우와, 1X2타일 2개로 채운 경우를 모두 구한다 
	ret = solve(n - 1) + solve(n - 2);
	ret %= MOD;

	return ret;
}

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

	//cache를 -1로 초기화 한다
	memset(cache, -1, sizeof(cache));

	int n;
	int result;

	cin >> n;

	result = solve(n);

	cout << result << "\n";

	return 0;
}