백준 11727 : 2xn 타일링 2

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

문제읽기

앗 저번 문제 2xn 타일링에서 발전한 문제다. 2x2 타일링이 추가되었다. 한번 살펴보자.

코드

#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] = ((2*(dp[i - 2]) + dp[i - 1]) % 10007);
	}
	cout << dp[n];
	return 0;
}

분석

보니까 가로로 누은 2개의 타일이 한개의 4x4 타일로 바뀔 수 있으므로 2*dp[i - 2]가 된다.

빠르게 저번 문제만 복습하고 넘어가는 용으로 확인하고 간다.