직사각형을 채우는 방법의 개수 구하기

다음 그림과 같은 타일을 이용하여 2 * 5 인 직사각형을 채우는 방법의 수를 구하여라

정답) 1944

 

문제풀이)

2 * 1 의 크기의 직사각형을 채우는 경우의 수를 확인해 보면 다음과 같이 3가지 이다.

삼각형 2개를 이용하는 경우 2가지

직사각형을 이용하는 경우 1가지

2 * 2 크기의 직사각형을 채우는 경우의 수를 확인 해 보면 2 * 1 을 f(1) 이라고 생각하고 2*0을 f(0) 이라고 생각하면 f(0) 은 공간이 없는 곳에 채우는 개수이므로 안채우는 경우 1가지 이므로

2 * 2 를 f(2) 라고 하면 f(2) 는 f(1) 에 2 * 1 짜리 직사각형 한가지를 붙이는 경우 f(1) * 3 이 된다.

또한 f(0) 에 붙이는 경우는 1*2 짜리 2개를 붙이는 경우를 생각해 보면 3 * 3 = 9 가지가 발생한다.

이렇게 규칙을 찾으면 f(3) = f(2) * 3 + f(1) * 3 * 3 인 것을 확인 할 수 있다.

따라서 f(n) = f(n-1) * 3 + f(n-2) * 3 * 3 의 점화식을 유도 할 수 있다.

이것을 테이블로 채워 나가 보면 다음과 같이 계산을 할 수 가 있다.

정답은 1944 가 된다.