문제 ❌

타일 채우기

후기 및 분석

일단 오만하게 생각을 해버려서 내가 생각한 경우의 수 이외에 다른거 없는거 같다라고 생각을 함.

특히 n이 4일때부터 고유의 모양이 나오는 부분을 간과를 함

계속 고유의 모양이 나오고

n이 6일때

dp[6] = dp[4] * 3 + 2 까지는 이해가감.

구글링하면 사람마다 어떻게 접근을 해서 푼지가 조금씩 다른데 아래 링크가 이해가 제일 잘됨.

https://dontdiethere.tistory.com/82
이 블로그 그림이 진짜 잘 설명되어있는듯

이 그림 보고 이해함.

근데 이해가 안가는 부분이 n == 2일 경우 고유의 모양 갯수를 곱하는데

( N x 2 ) * 2 이부분이 이해가좀 안간다..

이해안가는 부분 ❓

구글링해서 사람들 코드를 보면 다 dp[0] = 1이런식이던데 왜 이렇게 하는건지 도무지 이해가 안간다 0개면 그냥 0이지 왜 1을 넣음???

=> 이거 이유가 있는데 else문에서

for (int i = 4; i <= n; i = i + 2)
{
	cache[i] = cache[i - 2] * cache[2];
	for (int j = i - 4; j >= 0; j = j - 2)
	{
		cache[i] = cache[i] + (cache[j] * 2);
	}
}

inner loop의 계산하는 부분 때문에 cache[0] = 1넣어 준거임

cpp코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define MAX 31
#define endl "\n"

int cache[MAX];

int main()
{	
	int n;
	cin >> n;

	cache[0] = 1;
	cache[1] = 0;
	cache[2] = 3;
	cache[3] = 0;
	
	if (n % 2 == 1)
	{
		cache[n] = 0;
	}
	else
	{
		for (int i = 4; i <= n; i = i + 2)
		{
			cache[i] = cache[i - 2] * cache[2];
			for (int j = i - 4; j >= 0; j = j - 2)
			{
				cache[i] = cache[i] + (cache[j] * 2);
			}
		}
	}
	
	cout << cache[n];
	
	return 0;
}