다이나믹 프로그래밍 : : 타일링 문제

 

11726번: 2×n 타일링

문제

 

2 x n 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수 를 구하는 프로그램을 작성하시오.

아래 그림은 2x5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

해당 문제의 점화식을 세워보자.

2 x 1 크기의 직사각형을 채우는 방법은 2x1 타일 하나로 채우는 방법 하나이다.

2 x 2 크기의 직삭각형은 2x1 타일 2개 혹은 1x2 타일 2개로 두가지 이다.

 

여기서 규칙을 찾아야 하는데

만약 열이 N인 직사각형을 채운다고 하면

N-1번째까지 채운 방법에서는 오직 2x1 타일 하나만 들어올 수 있다.

또한 N-2번째까지 채운 방법에서는 1x2타일 두 개가 들어올 수 있다. 여기서 2x1 타일 두개를 넣는 방법도 있지 않나 생각할 수 있지만 해당 방법은 N-1번째까지 채운 방법에서 2x1타일을 한개 넣은 시점에서 들어갈 방법은 2x1타일 넣는 것 밖에 없기 때문에 이미 포함된 방법이다.

 

따라서 점화식을 세우면

D[n] = D[n-1] + D[n-2] 이다.