[백준 알고리즘] 11727 2*N 타일링 2

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

 

풀이

해당 문제는 지난번 포스팅한 2*N 타일링 문제와 동일한 DP 문제이다.

단 2*2 타일이 추가 되므로 하나만 더 고려해주면 되는데 

 

N번째 타일 인 경우 DP(N-2) 값을 더해주면 되었는데 +2인 경우에는 2가지 경우의 수가 있으므로 *2를 해주어야 한다

 

즉 DP(N) = DP(N-1) + DP(N-2)*2의 형태가 된다.

 

 

#include<iostream>

using namespace std;

int main() {

	/*
	맨 마지막에 2칸 또는 1칸을 사용한다.

	1 2 1 2 1 2 ...
	.....1 2
	1) 1 : 1가지
	2) 1 + 1 , 2 (2*1, 2*2) : 3가지
	3) 1 + 1 + 1 , 2(2*1, 2*2) + 1 ,  1 + 2(2*1, 2*2) : 5가지
	4) 1 + 1 + 1 + 1 , 1 + 2 + 1 , 2 + 1 + 1 (=dp(4)) | 1 + 1 + 2 , 2 + 2 (=dp(2)),

	i) i - 1 + 1 , i - 2 + 2

	n) n - 1 + 1 , n - 2 + 2

	but 2에는 2*2 일 수도 있고 2*1 일 수도 있다.
	
	*/
	//int Numarray[1001];
	int kindarray[1001];
	int Num;
	cin >> Num;

	kindarray[1] = 1;
	kindarray[2] = 3;

	for (int i = 3; i <= Num; i++) {
		
		kindarray[i] = (kindarray[i - 1] + (kindarray[i - 2]*2))%10007;

	}

	cout << kindarray[Num] << endl;
}

 

 

끝