[DP] 백준 - 2133 타일 문제 3*n !!복습필수!!

하...

이건 기존 2*n랑 다르게

4부터 짝수일 때마다 +2가지 씩 추가되는 건데..

점화식 너무 어렵고...ㅠㅠ 다른 사람 코드보고 겨우 풀었는데

완벽하게 이해도 안됨.. 스..트..레....스........

 

고딩때 포기한 점화식

아직까지 괴롭히는구나 ㅠㅠ휴

 

수학..수학..

수학/코딩 논리적으로 사고해서 일반화된 식을 뽑아내야하는데..

너무 어렵다 ㅠㅠ

 

다시봐야지...

 

// BJ 2133 타일채우기
// DP

#include <iostream>
using namespace std;

int arr[31];

int dp(int x) {

	if (x == 0) return 1;
	if (x == 1) return 0;
	if (x == 2) return 3;
	if (arr[x] != 0) return arr[x];

	int result = 3 * dp(x - 2); //원래 점화식

	// 4부터~짝수마다 원래 점화식에서 + 2 씩 추가되어서 나옴
	for (int i = 3; i <= x; i++) {

		if (i % 2 == 0) {
			result += 2 * dp(x - i);
		}
	}
	return arr[x] = result;

}

int main() {

	int N;
	cin >> N;
	cout << dp(N);

}