05.04. 2×n 타일링 [Dynamic Programming][백준 11726]

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

11726번: 2×n 타일링

 

Algorithm classification : Dynamic Programming

 

05.04.1. Problem

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

 

05.04.2. Input limit

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

 

05.04.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.04.4. Solution

생각해보면 n열의 공간을 채우는 경우의 수를 f(n)이라고 하면 제일 왼쪽(또는 오른쪽 : edge)을 가로블록 2개로 채운 경우의 수와 세로 블록 1개로 채운 경우의 수이므로 피보나치 수열입니다. 이전에 설명드렸던 01타일 문제와 유사하군요.

int dp[1001] ={0};

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