05.05. 2×n 타일링 2 [Dynamic Programming][백준 11727]

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

11727번: 2×n 타일링 2

 

Algorithm classification : Dynamic Programming

 

05.05.1. Problem

Write a program to count the number of ways to fill a 2×n rectangle with 1×2, 2×1, and 2×2 tiles.

 

05.05.2. Input limit

In the first line n is given. (1 ≤ n ≤ 1,000)

 

05.05.3. Output

In the first line, the remainder of dividing the number of ways to fill a 2×n rectangle by 10,007 is printed.

 

05.05.4. Solution

이전에 소개해드린 01타일, 2xn 타일링과 매우 유사한 문제입니다. 2xn 타일링 문제와의 차이점은 2*2 타일이 추가되었다는 점입니다. 즉, 2*2 타일이 어떻게 점화식으로 표현되는지만 신경쓰면 됩니다. 물론 초기값들도 다르겠죠. dp table의 dp[1] = 1, dp[2] = 3이 될 것입니다. 

int dp[1001] ={0};

void cal(int n){
	if(dp[n] != 0) return;
	cal(n-1);
	dp[n] = (dp[n-1] + (2*dp[n-2]%10007))%10007;
}