<Baekjoon>#2133 3n 타일 채우기 (3n Tiling) c

처음 타일링 문제를 접했을 때는 이게 도대체 뭐지? 하는 생각이 들었다. 동적 프로그래밍을 처음 접한 문제가 타일링 이었기 때문에 더욱 더 낯설고 이상(?)했다.

이 문제를 풀기 전에 #11726, #11727 2n 타일링을 먼저 공부해야 이해가 더 잘 된다. 타일링만으로도 엄청 많은 문제를 응용해서 낼 수 있을 것 같다.

타일링 문제의 경우 끝을 기준으로 나눠서 생각해야 한다.
3 x k 인 타일의 경우 3 x (k-2), 3 x 2

먼저 n=1 인 경우부터 본다
그림을 굳이 그리지 않고 생각해도 n이 홀수인 경우에는 만들 수 없다는 것을 알 수 있다.

n=2인 경우 3가지가 나온다
보통 타일링 문제의 경우 n이 2,3 인 경우까지 해보면 점화식이 나오는데 이 경우에는 4까지 해봐야한다.

n이 4인 경우를 보면 n=2일 때로 쪼갤 수 없는 모양이 2개 존재한다
n이 6일 때도 쪼갤 수 없는 모양이 2개 존재한다.

f[4]=3 x f[2] + 2 x f[0] = 11

n이 4,6,8,10... 등등 증가할 때마다 각각 쪼갤 수 없는 모양이 2개씩 존재한다.

따라서

f[n]=3 x f[n-2]+2 x f[n-4]+2 x f[n-6]+...+2 x f[0]

와 같은 점화식이 나온다.

(학교 다닐 때 교수님께서 만들어진 코드만 보면 쉽게 점화식을 도출하는 것 처럼 보이지만 정말 치열하게 생각하고 파고들어야 알 수 있는 거라고 했다..ㅠㅠ 진짜 어렵다)

#include<stdio.h>

int f[31];

int dp(int n) {

	if (n == 0) return 1;
	if (n == 1) return 0;
	if (n == 2) return 3;
	if (f[n]) return f[n];
	else {
		f[n] = 3 * dp(n - 2);
		for (int i = 4; i <= n; i += 2)
			f[n] += 2 * dp(n - i);
	}
	return f[n];
}
int main() {
	int n;
	scanf_s("%d", &n, 1);
	printf("%d", dp(n));

	return 0;
}