[동적계획법, 난이도 중하] 백준 11726번 2xn 타일링

이 문제에 동적계획법을 적용시키면

2x1, 2x2, 2x3, ... 2x(n-1),2xn

이런식으로 차례대로 이전 값을 이용하여 계산해 나가면 된다.

이전 타일값에 1x2, 2x1 타일을 붙일 수 있는 경우의 수를 따져보자.

 

위의 전체 타일의 넓이는 2xn이다.

그리고 갈색 타일의 넓이는 1x2, 2x1이다. 

이렇게 2x(n-1) 타일에 2x1 타일을 1개 추가하는 방법 -> 1가지

2x(n-2) 타일에 1x2 타일을 2개 추가하는 방법 -> 1가지

 

2x(n-2) 타일에 2x1 타일을 2개 추가하는 방법은 포함하지 않는다.

왜냐하면 이는 2x(n-1) 타일에 2x1 타일을 1개 추가하는 방법과 같은 경우이기 때문이다.

경우가 중복된다는 의미다.

 

즉 save[n]=save[n-1]+save[n-2] 라는 점화식이 나온다.

 

 

save[]에 값을 저장할 때마다 10007로 나눈 나머지 값을 저장하면 된다.

#include <iostream>
#define max(x,y) (x>y)? x:y
using namespace std;
int save[1001];
using namespace std;
int dp(int a){
	save[1] = 1;
	save[2] = 2;
	if (save[a] != 0) {
		return save[a];
	}
	else return save[a] = (dp(a - 1) + dp(a - 2))%10007;
}
int main() {
	int n;
	cin >> n;
	cout << dp(n);
}