백준 2133번 C++

백준 2133번 타일 채우기

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

2133번: 타일 채우기

정답 코드

#include<stdio.h>
int find(int a);
int dp[31];
int main() {
	int n;
	scanf("%d", &n);
	printf("%d", find(n));
}
int find(int a)
{    
    if(a==0)
        return 1;
    if(a==1)
        return 0;
    if(a==2)
        return 3;
	if (dp[a] != 0)
		return dp[a];
	dp[a] = 3 * find(a - 2);
	for (int x = 4; x <= a;x++) 
	{
		if (x % 2 == 0)
		{
			dp[a]+= 2 * find(a - x);
		}
	}
	return dp[a];

}

문제 풀이

dp를 이용하는 문제이면서, 수학적인 사고력을 요구하는 문제입니다. 주어진 숫자들의 예시를 보면서 공식을 찾아야 합니다.
1)3가지 패턴이 이전 칸인 6칸 경우에 채워들어가므로 6칸 경우 * 3만큼 채워집니다. + (41 * 3)

2) 4칸에서 발생한 족보없는 패턴 2가지가 4칸 경우 * 2만큼 채워집니다. + (11 * 2)

3) 6칸에서 발생한 족보없는 패턴 2가지가 2칸 경우 * 2만큼 채워집니다. + (3 * 2)

4) 8칸에서도 족보없는 패턴이 2가지가 나오므로 +2를 해줍니다.