[알고리즘] tiling

세로 길이 2, 가로 길이 n인 2 x n 보드가 있고,
2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴.

n = 2 이면 2가지
n = 4 이면 5가지

문제풀이 순서

1. 경우의 수를 구할 타일 배치가 어떤 방식으로 이루어지는지 파악
: 타일은 2*1의 크기이고, 가로로 배치하거나 세로로 배치하거나는 상관이 없다고 한다.

🤔 n이 3일 때 경우의 수는 아래와 같다.

2. n과 n-1과 n-2의 경우의 수들이 이어져 있음을 파악
: 처음에 문제를 접했을 때 보드 위에 타일을 채우는 것에 대해서만 생각했는데, 차례대로 경우의 수를 구해보면 0, 1, 2, 3, 5, 8... 순으로 규칙이 있는 숫자들이 나타난다. 피보나치 수열처럼 2보다 큰 n의 값은 n-1의 값과 n-2의 값을 더한것과 같다.

function tiling (n){
 
  //규칙이 적용되지 않는 0부터 2까지는 미리 배열에 저장해둔다.
 let arr = [0,1,2];
 
  
 for(let i=3; i<=n;i++){
   arr[i] = arr[i-1]+arr[i-2];
 }
return arr[n];
}

위처럼 풀 수도 있지만, sub 함수를 하나 더 만들어 준 뒤 재귀를 이용해서 풀이할 수도 있다.
이렇게 풀이할 때 이미 구한 값을 다시 구하지 않기 위해서 메모이제이션이라는 개념이 필요한데, '주어진 입력값에 대한 결과를 저장함으로써 같은 입력값에 대해 함수가 한 번만 실행되는 것을 보장'하는 것이라고 한다.

function tiling(n){
  
	const save = [0, 1, 2]; 
  
	function subTiling(size){
    	if(save[size] !== undefined) return save[size]; // 이미 해결한 문제는 풀지 않도록 조건을 걸어준다. 
    if(size <= 2) return save[size];
    save[size] = subTiling(size-1) + subTiling(size-2);
    return save[size];
  }
  return subTiling(n);
};
 
}