tiling

세로 길이 2, 가로 길이 n인 2*n 보드가 있다.
2*1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 구하라

그림을 그려가며 문제를 풀다보니 n번째 타일은 n-1번째와 n-2번째의 타일 수의 합이라는 것을 발견할 수 있었다.

피보나치와 비슷한 구조라고 생각하고 문제를 풀었다.
시간복잡도가 O(N) 이 나오기 위해서는
memoization, tabulation, slicing window
이렇게 3가지 방법이 존재한다.