[Gold / 2133] 타일 채우기

문제 링크

---

🔷 분류

다이나믹 프로그래밍

✒️ 문제 설명

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

⬅️ 입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

➡️ 출력

첫째 줄에 경우의 수를 출력한다.

💻 코드 (C++)

#include <iostream>
using namespace std;
// DP 테이블
int dp[31];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	if(n % 2 != 0) { // 홀수면 경우 X
		cout << 0; 
		return 0;
	} else { 
		dp[0] = 1;
		dp[2] = 3;
		for(int i = 4; i <= n; i += 2) {
			dp[i] = (dp[i-2] * dp[2]); 
			for(int j = 4; j <= i; j +=2) {
				dp[i] += (dp[i-j] * 2);
			}
		}
		cout << dp[n];
		return 0;
	}
}