세로 길이 2, 가로 길이 n인 2 x n 보드가 있습니다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 합니다.
let tiling = function (n) {
// 2 x n 보드를 2 x 1 타일로 채우려면
// n = 1일 때 1가지, n = 2일 때 2가지(가로, 세로)
// n = 3일 때 3가지, n = 4일 때 5가지
const memo = [0, 1, 2];
// 경우의 수를 저장하는 변수
const aux = (size) => {
if (memo[size] !== undefined) return memo[size];
// 이미 경우의 수가 저장되어 있는 값이면 바로 꺼내서 리턴
if (size <= 2) return memo[n];
// 2보다 작을 때도 이미 저장해주었으므로 바로 꺼내서 리턴
memo[size] = aux(size - 1) + aux(size - 2);
// 경우의 수가 저장되어 있지 않으면 피보나치 수열로 더해서 리턴
return memo[size];
};
return aux(n);
};