studyHard
article thumbnail
Tiling
알고리즘 2023. 4. 14. 16:03

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