백준 11726 - 2xn 타일링

https://www.acmicpc.net/problem/11726

 

동적 계획법으로 푸는 문제

 

2xk 크기의 직사각형 ak을 타일링 하는 경우의 수 dp[k]는 두 가지 방법을 통해 구할 수 있다.

 

1) a(k-1)에서 뒤에 2x1 직사각형을 추가

2x1 직사각형을 타일링 하는 방법은 1가지밖에 없으므로, 이 때의 경우의 수는 dp[k-1]이다.

 

2) a(k-2)에서 뒤에 2x2 직사각형을 추가

2x2 사각형을 타일링 하는 방법은 1x2 타일 2개 사용, 2x1 타일 2개 사용의 2가지이다.

 

따라서 직사각형 a(k-2)를 채우는 모든 경우에 대해 2가지 경우가 생성된다.

이 때 2x1 타일(세로로 긴 타일)을 2개 사용하는 경우는

a(k-1)에서 뒤에 2x1 직사각형을 추가하는 경우에 포함되므로 계산에서 제외한다.

따라서 경우의 수는 dp[k-2]이다.

 

위 두 방식을 이용해 dp[k]를 계산하는 점화식 dp[k] = dp[k-1] + dp[k-2]를 구할 수 있으며, 이를 이용해 프로그램을 작성한다.

 

배운 내용 :

동적 계획법에서 겹치는 부분 파악하기