03. 동적계획법 - 예제4

[1. 문제 설명]

2xN 크기의 직사각형을 2x1 크기의 타일로 채울 때

좌우 대칭으로 채우지 않는 경우의 수를 구한다.

 

비대칭 타일링 방법의 수를 1,000,000,007 로 나눈 나머지

(1e9 + 7)

 

[2. 풀이 접근]

A. 여사건 방식

전체 타일링 방법에서 대칭 타일링 방법의 수를 빼서 구한다.

 

대칭 타일링 수는 n 이 짝수인 경우와 홀수인 경우를 나누어서 생각한다.

n 이 짝수인 경우

=> 가운데를 가로 타일링으로 채우고, 한쪽을 채운 뒤, 나머지 한쪽을 동일하게 채우는 방식

=> 절반 한쪽을 채우고, 나머지 한쪽을 마찬가지로 동일하게 채우는 방식

 

n 이 홀수인 경우

=> 가운데러르 세로 타일링을 채우고, 한쪽을 채운 뒤, 나머지 한쪽을 동일하게 채우는 방식

 

== 전체 계산 후 주의할 점 ==

빼는 연산에서 값이 음수가 될 수 있다.

그러나 답은 음수가 될 수 없다.

나머지를 구할 때 사용 할 수 를 더해서 값을 보강해야 한다.

 

 

B. 비대칭만 계산

=> 잘못된 접근

=> 모든 타일링 방법을 만들어 보고, 좌우 대칭이 아닌 것을 제외한다.

=> 그러나, 이 방법은 메모이제이션을 적용 할 수 없다.

=> 대칭 판단을 위해 과거에 선택한 조각들의 정보를 전달해야 하기 때문...

 

B.1 맨 앞에서부터 채우는 것이 아니라, 양쪽 끝에서 부터 동시에 만들어나가야 한다.

B.1.A 양쪽 끝을 세로 타일링 하는 방법 => 내부가 비대칭이어야 한다.

B.1.B 양쪽 끝을 가로 타일링 하는 방법 => 내부가 비대칭이어야 한다.

B.1.C 왼쪽 끝을 세로, 오른쪽 끝을 가로로 타일링 한다 => 이미 비대칭이므로, 내부는 어떻게 채우든 상관 없다.

B.1.D 왼쪽 끝을 가로, 오른쪽 끝을 세로로 타일링 한다 => 이미 비대칭이므로, 내부는 어떻게 채우든 상관 없다.

 

 

[3. 코드]