Algorithm/유형별 : DP

[C++] [DP] 백준 2133번 : 타일 채우기

쟌쥰 2020. 2. 2. 13:32

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

 

2133번: 타일 채우기

문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다....

www.acmicpc.net

#include<iostream>
using namespace std;

int d[31];

int dp(int n) {
	if (n == 0) return 1;
	if (n == 1) return 0;
	if (n == 2) return 3;

	if (d[n] != 0) return d[n];

	int result = 3 * dp(n - 2);
	for (int i = 3; i <= n; i++) {
		if (i % 2 == 0)
			result += 2 * dp(n - i);
	}

	return d[n] = result;
}

int main(void) {
	int n;
	cin >> n;
	cout << dp(n) << endl;
}