[BAEKJOON] 11727 2*n 타일링 2

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> using namespace std; int main() { int n; scanf("%d", &n); vector<int>DP(1001, -1); DP[1] = 1; DP[2] = 3; for (int j = 3; j <= n; j++) DP[j] = (DP[j - 2] * 2 + DP[j - 1])%10007; printf("%d", DP[n]); return 0; }

타일링 문제는 피보나치이다.

이 문제는 2*2의 경우의 수도 더해야하기 때문에 

피보나치에서 조금 변형해야한다.