11727번: 2×n 타일링 2

문제:

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

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

입력:

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

풀이:

• 이 문제는 #11726: 2×n 타일링과 푸는 방식은 동일하다. 따라서 이 문제를 처음 푸는 것이면 #11726: 2×n 타일링를 먼저 풀어보고 오는 것을 추천한다.
• 이 문제와 #11726: 2×n 타일링 2의 차이점은 가로가 2칸인 경우에 한가지 경우가 더 추가 되었다는 것인데 그러면 n이 2일 때 base case를 3으로 바꿔주면 된다. 또한, 이전에는 가로가 2칸일 때와 1칸일 때 겹치는 경우의 수가 한개 있어서 가로가 2칸일 때 경우의 수가 사실상 1개였지만 이번에는 2개이기 때문에 재귀함수에서 n-2일 때 곱하기 2를 해준다.

코드:

#include <iostream>

using namespace std;

int d[1001]; //바텀업인경우 = {0,1,3}

//탑다운 방식의 재귀 함수
int dp(int n){
	if(n==1) return 1; //시작하는 칸이 1칸인 경우 경우의 수 1개
	if(n==2) return 3; //시작하는 칸이 2칸인 경우 경우의 수 3개
	if(d[n]) return d[n]; //이미 값이 존재할 경우 배열에서 찾아옴
	return d[n] = (dp(n-1)+2*dp(n-2))%10007; //한칸인 경우와 두칸인 경우로 나눠 경우의 수 확인

}

int main(void){
	int n;
	//입력
	cin >> n;

	/* 바텀업 방식
	for(int i = 3; i<=n; i++){
		d[i] = (d[i-1]+2*d[i-2])%10007; //한칸인 경우와 두칸인 경우로 나눠 경우의 수 확인
	}
	cout<<d[n];
	*/

	//출력
	cout<<dp(n);
}