(c++)백준 11726번: 2xn 타일링

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

11726번: 2×n 타일링

dp[i] : 2xi 크리 직사각형을 1x2, 2x1 타일로 채우는 방법의 수

 

dp[1] :

1개

 

dp[2] :

 

2개

 

dp[3] :

 

 

3개

 

dp[4] 부터는 처음 타일이 2x1 한 개로 채워지는 경우와 1x2타일 두 개로 채워지는 경우로 나뉨

※ 2x1 한 개로 채워지는 경우 남은 직사각형은 dp[x-1]의 경우의 수로 채워짐

※ 1x2 두 개로 채워지는 경우 남은 직사각형은 dp[x-2]의 경우의 수로 채워짐

점화식

dp[x] = dp[x-1] + dx[x-2] (x≥4) 

#include <iostream>
using namespace std;

int n;
int dp[1001];

void DP() {
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;
	for (int i = 4; i <= n; i++) {
		//처음 타일이 2*1타일일 경우와 1*2타일 두개일 경우 
		dp[i] = (dp[i - 1] + dp[i - 2])%10007;
	}
	cout << dp[n] << endl;
}

int main() {
	cin >> n;
	DP();
	return 0;
}