주어진 넓이를 주어진 타일로 채우는 문제인 타일링은 재귀적 사고방식으로 봐야 패턴을 확인 할 수 있다.
f(1), f(2), f(3)... 같이 순차적으로 값을 파악하기보다
f(n), f(n-1), f(n-2) 같이 역순으로 파악하며 구조와 패턴을 찾아야 한다.
타일링의 패턴을 찾기위해 거쳐야 하는 과정은 다음과 같다.
맨 마지막에 들어갈 수 있는 타일의 경우의 수 찾기 => 넓이가 증가할 때마다 나타나는 특이 케이스 찾기
2xn 타일링
2 x 1 크기의 직사각형 타일로 2xn 넓이를 채우는 경우의 수의 개수 구하기
2xn을 채우는 경우의 수 개수 = f(n)
f(n)에서 마지막에 오는 타일의 경우의 수는 두 가지 경우밖에 없다.
- 한 개가 세워져 있는 경우
- 두 개가 눕혀져 있는 경우
이런 패턴으로 보면 f(n)은 f(n-1)의 모든 경우의 수 + f(n-2)의 모든 경우의 수가 된다.
맨 뒤 타일은 고정되어 있기 때문에 그 앞의 경우의 수만 구하면 되기 때문이다.
즉 피보나치의 수 공식과 같다. f(n) = f(n-1) + f(n-2)
💡 타일이 2 x 1 & 2 x 2 인 경우
맨 끝에 들어갈 수 있는 경우의 수는 아래와 같다.
- 2 x 1 세워서 한 개 => f(n-1)
- 2 x 1 눕혀서 두 개 => f(n-2)
- 2 x 2 한 개 => f(n-2)
f(n) = f(n-1) + f(n-2) * 2
초기값: f(1) = 1, f(2) = 3
