BOJ 2718 - 타일 채우기

링크: https://www.acmicpc.net/problem/2718

[이전 게시글로부터 글 옮김]

2x1 크기의 타일로 4xN 크기의 타일을 채우는 경우의 수를 구하는 문제이다.

문제를 작은 문제로 쪼개야하는 데 발상보다는 과정이 쉽게 떠오르지 않아서 해결하는 데 오랜 시간이 걸렸다.

2xN 타일 크기의 문제와 똑같이 왼쪽부터 1줄씩 채워나가면서 완성해나간다. 하지만 이 문제는 높이가 4N이기 때문에 1줄을 채울 때 여러 개의 경우가 나온다.

[그림 1] 한 줄의 상태를 비트로 표현할 때의 정수

 외의 경우(1010 이나 0001 등의 형태)는 나올 수 없다. 왜냐하면 "이전의 줄의 모든 칸은 채워져있다."라는 가정에서 나타나는 상태이기 때문이다. 이 가정이 성립하지 않으면 타일은 채워질 수 없다. [그림 1]에서 점은 빈 칸이고, x는 이미 타일로 채워진 칸이다 (그것이 어떠한 형태이건 채워졌다라는 상태만 의미한다.)

물론 [그림 1] 에서 1111 은 빠져있다. 필자는 1111을 0000과 동일한 상태로 봤기 때문이다. N일때 한 줄의 모든 칸이 다 차있다(1111)면 이것은 (N-1)에 대한 문제가 된다. - 자세한 것은 2N 타일링 문제 풀이 참조 - 따라서 1111 일때는 다음의 다음 칸(N-2)의 상태가 0000인 것과 같다.

그럼 한 줄의 상태로 모든 상태를 어떻게 표현하는가?

앞으로 채워야할 오른쪽의 타일에 대해 (위처럼 0000과 같이 표현된) 현재 상태로부터 진행될 수 있는 경우는 아래 그림과 같다.

[그림 2] 어떠한 상태로부터 진행될 수 있는 타일의 새로운 상태

파란색 점선 박스를 다음으로 채울 오른쪽 줄이라고 하자. 그럼 0000 으로부터 나오는 경우는 1001, 1100, 1111, 0011, 0000 과 같다. 마찬가지로 나머지 경우도 동일하다.

그렇다면 문제는 아래와 같이 쪼개어 표현이 가능하다.

f(N칸을 채우는 경우, 현재 상태) = 현재 상태로부터 만들 수 있는 다음 상태(N-1)의 개수

N이 0이 되는 순간 모든 줄을 확인했다는 의미이고 이 때의 상태가 0000(혹은 1111)이면 모든 줄을 채웠다는 의미이므로 하나의 개수로 치고, 그 외에는 잘못된 경우이다.

0000 -> 1111 -> 0000 을 한번에 넘어가는 N-2 때문에 N < 0 인 경우가 나온다. 이 때는 상태에 상관없이 불가능한 경우이므로 0 이다.

같이 보기

1793번: 타일링 (2xN 크기)

2133번: 타일 채우기 (3xN 크기)