#11727 2xn 타일링 2

# 문제

# 입력 및 출력

# 풀이

저번에 풀었던 문제에서 조금 추가된 문제다

날려써서ㅋㅋㅋ

2x1 타일 한개로 끝나는 경우는 dp[n-1]가지

1x2 타일 두개로 끝나는 경우는 dp[n-2]가지

2x2 타일 한개로 끝나는 경우는 dp[n-2]가지가 됨

따라서 점화식은 dp[i] = dp[i-1] + dp[i-2] * 2가 됨

#include <iostream>
using namespace std;
int dp[1001];

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

전에 한번 풀었던 문제라 쉽게 풀었음