11727번 2xn 타일링 2

 

11727번: 2×n 타일링 2

DP문제를 연습하고 있다만 설명의 과정이 귀찮아 블로그에 기록하진 않았다.

 

이번 문제는 설명하기가 간단하고, DP의 핵심적인 부분을 다루고 있다.

 

블럭이 한 칸(2x1) 증가하는 경우와 두 칸(2x2)씩 증가하는 경우, 2가지를 상정한다.

 

이 때 두 칸씩 늘어나는 경우는 가로로 누운 블럭 두 개가 붙은 경우와 큰 하나의 블럭, 두 가지 블럭이다.

 

길이i 타일 = 길이가 i-1인 타일에 한 칸을 붙인 경우(경우의 수는 그대로) + 두 칸씩 늘어나는 경우*2(두 가지 블럭)

 

점화식으로 표현하면

 

DP[i] = DP[i-1] + DP[i-2]*2

 

#include <iostream>
using namespace std;
int arr[1001];
int main() {
	int n;
	cin >> n;
	arr[1] = 1; arr[2] = 3;
	for (int i = 3; i <= 1001; i++)
		arr[i] = (arr[i - 1] + arr[i - 2] * 2) % 10007;
	cout << arr[n] ;
	return 0;
}