[백준]Baekjoon11727(Dynamic Programming)

11726과 거의 흡사한 문제

11726문제에 2x2 타일 하나가 추가 됐을 뿐이다.

고로 2x2의 공간을 한번에 채우는 경우가 2x1 두개, 2x2 하나

총 2가지로 늘었으며 이것을 점화식에 반영하면

f(n) = 2*f(n-2) + f(n-1)이 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

int memo[1001];
int main()
{
	int n; 
	cin >> n;
	memo[1] = 1; memo[2] = 3;
	for (int i = 3; i <= n; i++) {
		memo[i] = (2*memo[i - 2] + memo[i - 1])%10007;
	}
	cout << memo[n] << '\n';
}