(c++)백준 11727번: 2xn 타일링 2

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

11727번: 2×n 타일링 2

2020/06/08 - [백준/DP] - 11726 2xn 타일링

기존 2xn 타일링에 경우의 수 하나 더 추가해주면 되는 문제.

※2x2타일로 시작하면 dp[x-2]만큼 경우의 수 있음

#include <iostream>
using namespace std;

int n;
int dp[1001];

void DP() {
	dp[1] = 1;
	dp[2] = 3;
	dp[3] = 5;
	for (int i = 4; i <= n; i++) {
		//처음 타일이 2*1타일일 경우 + 1*2타일 두개일 경우 + 2*2타일일 경우
		dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
	}
	cout << dp[n];
}

int main() {
	cin >> n;
	DP();
	return 0;
}