[백준] 11727 2 x n 타일링 2

문제링크] https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

---

문제요약

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 문제입니다.

 

백준 11726 문제와 마찬가지로 다이나믹 프로그래밍을 이용한 알고리즘 문제이다. 

2019/07/30 - [컴퓨터/알고리즘] - [백준] 11726 2 x n 타일링

[백준] 11726 2 x n 타일링

풀이

가로 길이가 1만큼 늘어날 때 타일을 채울 수 있는 경우의 수는 한 가지이다.

가로 길이가 2만큼 늘어날 때 타일을 채울 수 있는 경우의 수는 두 가지이다.

 

따라서 점화식은 

D[n] = D[n-1] + 2D[n-2]

이라고 세울 수 있다.

 

코드는 c/c++로 작성하였습니다.

#include <stdio.h>

int arr[1001];

int dp(int x) {
	if (x == 1) return 1;
	if (x == 2) return 3;
	if(arr[x]!=0) return arr[x];
	return (arr[x] = (2*dp(x - 2) + dp(x - 1))%10007);
	
}
int main() {

	int num;
	scanf("%d", &num);
	printf("%d", dp(num));

	return 0;
}