백준 11726번 : 2xn 타일링

문제 접근

---

C(n) = (2-1)*C(n-2) + C(n-1) = C(n-2) + C(n-1) 이라는 점화식이 나온다. 이유는 C(n-2) 블럭에 2개짜리를 붙이는 경우와, C(n-1) 블럭에 1개짜리를 붙이는 경우를 더한 것에 중복을 제거한 게 C(n) 이기 때문이다. 중복은 2개짜리를 붙일 때 가로 2개와 세로 2개를 붙일 수 있는데 세로 2개는 1개를 붙이는 경우와 중복되기에 2개를 붙일 때 2가지 경우 중 하나는 제외한다. 따라서 위와 같은 점화식이 나오는 것이다.

 

 

문제 코드

---

#include <iostream>
#include <algorithm>

using namespace std;

int cache[1000];

int dp(int n)
{
	int& res = cache[n];
	
	if(n<3)
		return n;
	
	if(res!=-1)
		return res;
	
	return res = (dp(n-1) + dp(n-2))%10007;
}


int main(void)
{
	fill(cache, cache+1001,-1);
	
	int n;
	
	cin>>n;
	
	cout<<dp(n)<<'\n';
}